يأخذ Farmer John أبقاره $N$ المرقمة $1\ldots 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