소 장기자랑

농부 존이 소 $N$마리를 데리고 군 축제에서 열리는 소 장기자랑에 나간다. 소에는 $1$번부터 $N$번까지 번호가 붙어 있고, $i$번 소의 무게는 $w_i$, 재능은 $t_i$이며 둘 다 정수이다.

올해 장기자랑 규칙은 다음과 같다.

(i) 무대에 올리는 소 그룹은 무게 합이 $W$ 이상이어야 한다. 뛰어난 소 한 마리만으로는 이길 수 없게 만든 규칙이다.

(ii) 재능 합을 무게 합으로 나눈 비율이 가장 큰 그룹이 우승한다.

존의 소를 모두 합치면 무게가 $W$ 이상이므로 규칙 (i)을 만족하는 그룹은 반드시 있다. 규칙 (i)을 만족하는 그룹으로 낼 수 있는 재능 합 대 무게 합 비율의 최댓값을 구하라.

첫째 줄에 $N$ ($1 \le N \le 250$)과 $W$ ($1 \le W \le 1000$)가 주어진다. 다음 $N$개 줄에는 각각 소 한 마리를 나타내는 두 정수 $w_i$ ($1 \le w_i \le 10^6$)와 $t_i$ ($1 \le t_i \le 10^3$)가 주어진다.

무게 합이 $W$ 이상인 그룹으로 얻을 수 있는 재능 합 대 무게 합 비율의 최댓값을 $A$라 하자. 출력을 정수로 유지하기 위해 $1000A$의 내림값을 출력한다. 내림은 소수 부분을 버려 정수로 내리는 연산이며, 이미 정수인 값은 그대로 둔다.

첫 번째 예제에서 비율만 따지면 재능 11, 무게 10인 소 한 마리가 가장 좋다. 그러나 무게 합이 15 이상이어야 하므로 그 소에 재능 21, 무게 20인 소를 더한 그룹이 최적이 된다. 이 그룹의 비율은 $(11+21)/(10+20) = 32/30 = 1.0666\ldots$이고, 1000을 곱해 내림하면 1066이다.