25312번 - 200% Mixed Juice!

문제

음료수가 담긴 병이 총 $N$개 있다. $i$번째 병에는 음료수가 총 $w_i$l만큼 담겨있고, 음료수에는 설탕이 총 $v_i$mg만큼 들어 있다. 이 음료수들 중 일부를 섞어서 총용량이 정확히 $M$l인 혼합 음료수를 만들려고 한다. 이때, 병에 있는 음료수를 일부만 사용해도 된다.

혼합 음료수의 설탕량은 섞은 음료수들 각각에 들어 있는 설탕량의 합으로 결정된다. 설탕은 음료수에 균일하게 녹아 있기 때문에, 어떤 병에 든 음료수를 일부만 사용할 경우 설탕 역시 그 비율만큼 들어가게 된다. 즉, $i$번째 음료수를 $a_i$l만큼$(0 \le a_i \le w_i)$ 섞는다면, $i$번째 음료수에 해당하는 설탕량은 $\left(\frac{a_i}{w_i} \times v_i\right)$mg이다.

음료수를 섞어 총용량이 정확히 $M$l인 혼합 음료수를 만들었을 때, 여기에 들어갈 수 있는 설탕량의 최댓값을 출력하여라.

입력

첫 줄에는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100,000円;$ 1ドル \le M \le w_1 + w_2 + \cdots + w_N)$

다음 $N$개의 줄의 $i$번째 줄에는 두 정수 $w_i$와 $v_i$가 공백으로 구분되어 주어진다. $(1 \le w_i, v_i \le 100,000円)$

출력

총용량이 정확히 $M$l인 혼합 음료수에 들어갈 수 있는 설탕량의 최댓값을 기약분수로 표현했을 때 $\left(\frac{a}{b}\right)$mg이라고 하자. 이때 $a$와 $b$를 /를 사이에 두고 차례로 출력한다.

제한

힌트