Farmer John은 $1\ldots N$으로 번호가 붙은 $N$마리 소를 군 축제의 연례 소 재능 쇼에 데려갑니다. 소 $i$의 무게 $w_i$와 재능 $t_i$는 정수입니다.

새 규칙에 놀랐습니다.

(i) 총무게가 적어도 $W$인 팀이어야 합니다. 강한 개인뿐 아니라 강한 팀이 경쟁하게 하려는 것입니다.

(ii) 총재능 대 총무게 비율이 가장 큰 팀이 이깁니다.

모든 소의 무게 합은 $W$ 이상이므로 (i)를 만족할 수 있습니다. 그런 팀의 최대 비율을 구하세요.

입력

첫 줄에 $N$ ($1 \leq N \leq 250$), $W$ ($1 \leq W \leq 1000$). 다음 $N$줄은 정수 $w_i$ ($1 \leq w_i \leq 10^6$), $t_i$ ($1 \leq t_i \leq 10^3$).

출력

무게가 적어도 $W$일 때 최대 비율을 구합니다. 답이 $A$면 $1000A$의 바닥 값을 출력하여 정수가 되게 합니다. 바닥 연산은 정수가 아닐 때 소수 부분을 버리고 아래 정수로 내림합니다.

예제

입력 1

3 15
20 21
10 11
30 31

출력 1

1066

참고

재능 11, 무게 10인 소 혼자가 최고지만 무게 15 이상이 필요하므로 재능 21, 무게 20인 소도 선택합니다. $(11+21)/(10+20)=32/30=1.0666666...$에 1000을 곱해 내리면 1066입니다.

문제 작성: Brian Dean