버그 수정하기

한 대형 소프트웨어 회사가 주력 제품의 새 버전 출시를 준비하고 있다. 이 프로젝트에 새로 합류한 개발자인 당신은, 새 버전이 나가기 전에 고쳐야 할 미해결 버그 목록을 받았다.

버그이다 보니 몇 가지 아이디어는 있어도 정확히 어떻게 고칠지는 확실하지 않다. 각 버그에 대해 당신은 그 버그를 빠르게 고칠 수 있을 확률을 추정할 수 있다. 이 추정은 틀릴 수 있어서, 어떤 버그를 시도했다가 실패하면 그 버그에 대한 추정치를 낮추게 된다.

이 과정을 다음과 같은 확률 모형으로 표현한다. 각 버그에는 현재 수정 확률 $p$가 있다. 매 시간마다 당신은 미해결 버그 하나를 골라 그 한 시간 동안 그 버그에 매달린다(한 시간이 되기 전에 고치면 남은 시간은 쉬며 보낸다). 그 시간 안에 버그를 고칠 확률은 $p$이다. 실패하면 그 버그의 수정 확률에 계수 $f$($0 \le f \le 1$)가 곱해져 $p \cdot f$가 되고, 다른 버그들의 수정 확률은 그대로 유지된다. 다음 시간에도 다시 미해결 버그 하나를 골라 작업하며, 새 버전이 출시될 때까지 이를 반복한다.

각 버그에는 그것을 고치는 것이 얼마나 가치 있는지를 나타내는 심각도 $s$도 있다. 출시 전에 모든 버그를 다 고치지 못할 수도 있으므로, 상사에게 최대한 좋은 인상을 주기 위해 당신은 매 시간 작업할 버그를 신중히 골라 고쳐낸 버그들의 심각도 합을 최대화하려 한다. 매 시간 이 값을 최대화하도록 작업할 버그를 고른다고 할 때, 당신이 고치는 버그들의 심각도 합의 기댓값은 얼마인가?

첫 줄에는 세 수 $B$, $T$, $f$가 주어진다.

• 정수 $B$ ($0 \le B \le 10$): 미해결 버그의 수,
• 정수 $T$ ($0 \le T \le 100$): 출시까지 남은 시간(시간 단위),
• 실수 $f$ ($0 \le f \le 1$): 위에서 설명한 계수.

이어지는 $B$개의 줄에는 각 버그가 두 수 $p$와 $s$로 주어진다. 실수 $p$ ($0 \le p \le 1$)는 그 버그의 초기 수정 확률이고, 정수 $s$ ($0 \le s \le 10000$)는 그 버그의 심각도이다.

당신이 고치는 버그들의 심각도 합의 기댓값을, 이 값을 최대화하도록 작업했을 때의 최댓값으로 소수점 아래 여섯 자리까지 반올림하여 출력한다.