드론 비행

당신은 방금 배터리로 작동하는 새 드론을 얻었지만, 배터리가 없다. 상점에는 드론에 사용할 수 있는 배터리가 $N$개 있으며, 각 배터리의 에너지는 $e_i$, 무게는 $w_i$, 가격은 $c_i$이다. 상점에는 각 배터리가 하나씩만 있다.

드론을 최대한 오래 즐기기 위해서는 완전히 충전했을 때 드론이 당연히 가능한 한 오래 비행하기를 바랄 것이다. 드론이 공중에 머무를 수 있는 시간은 식 $t = \frac{E_{tot}}{W_{tot}}$로 주어진다. 여기서 $E_{tot}$는 드론의 모든 배터리가 가진 에너지의 총량이고, $W_{tot}$은 드론과 배터리의 무게를 합한 값이다.

예산 $B$와 드론 자체의 무게 $W$가 주어질 때, 드론이 비행할 수 있는 최대 시간을 구한다.

점수

여러 테스트 케이스 그룹으로 풀이를 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$10$| $N \leq 20$

$2$ |$20$| $w_i = 0$

$3$ |$20$| $c_1 = c_2 = \dots = c_N$

$4$ |$50$| 추가 제한 없음.

첫 번째 줄에는 세 정수 $N$, $B$, $W$ ($1 \leq N \times B \leq 200,000$ 및 $1 \leq W \leq 1000$)가 주어진다. 각각 사용 가능한 배터리의 수, 예산, 드론의 무게이다.

이어지는 $N$개의 각 줄에는 세 정수가 주어진다. $i$번째 줄에는 $e_i$, $w_i$, $c_i$ ($0 \leq e_i \leq 1000$, $0 \leq w_i \leq 1000$, $0 \leq c_i \leq B$)가 주어지며, 각각 배터리 $i$의 에너지, 무게, 가격이다.

배터리를 최적으로 선택했을 때 드론을 비행시킬 수 있는 최장 시간을 십진수로 출력한다. 답의 상대 오차 또는 절대 오차가 최대 $10^{-5}$이면 정답으로 인정된다. 즉, 출력한 답이 $a$이고 정답이 $b$일 때, $|a-b| \leq 10^{-5}$ 또는 $\frac{|a-b|}{|b|} \leq 10^{-5}$ 중 하나가 성립하면 정답으로 인정된다.