문제 세트 구성

당신은 심판으로서 대회의 문제 세트를 구성한다. 후보 문제들이 여럿 있다. 각 문제에 대해, 어떤 팀이 그 문제를 풀 수 있을 확률과, 풀 수 있다면 해결책을 구현하는 데 걸리는 시간을 알고 있다. 모든 구현 시간은 서로 다르다.

모든 팀이 문제 세트를 마주했을 때 취하는 전략을 알고 있다. 먼저, 그들이 풀 수 있는 문제의 집합을 결정한다(대회 시작 시점에 즉시 할 수 있다고 가정한다). 그런 다음, 시간 제한 내에 풀 수 있는 문제를 최대한 많이 푼다. 시간 제한 내에 풀 수 있는 부분집합이 여럿이라면, 먼저 풀 수 있는 문제 수로 동점을 깨고, 그다음에는 그 문제들을 모두 푸는 데 걸리는 총 시간을 최소화하는 쪽으로 동점을 깬다.

어떤 문제의 난이도를, 그 문제가 풀에서 균등하게 무작위로 선택된 $k-1$개의 다른 문제와 함께 크기 $k$의 문제 세트에 포함되었을 때 팀이 그 문제를 풀 확률로 정의한다. 모든 문제의 난이도를 구하라.

첫 줄에 세 정수 $n$, $k$ ($1 \le k \le n \le 50$)와 $t$ ($1 \le t \le 2500$)가 주어진다. $n$은 풀에 있는 문제 수, $k$는 세트에 선택할 문제 수, $t$는 대회의 시간 제한이다.

다음 $n$개의 줄에는 각각 실수 $p$ ($0.0 \le p \le 1.0$)와 정수 $s$ ($1 \le s \le t$)가 주어지며, 이는 문제를 나타낸다. $p$는 팀이 그 문제를 풀 수 있을 확률이고, $s$는 푸는 데 걸리는 시간이다. 확률은 소수점 이하 최대 네 자리까지 주어진다. 모든 풀이 시간은 서로 다르다.

입력 순서대로 각 문제의 난이도를 한 줄에 하나씩 $n$줄에 걸쳐 출력한다. 각 값은 절대 오차 또는 상대 오차 $10^{-6}$ 이내여야 한다.