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

Note

כישרון 11 ומשקל 10 מיטביים לבדם, אך צריך משקל 15, לכן מוסיפים כישרון 21 ומשקל 20. $(11+21)/(10+20)=32/30=1.0666666...$, כפול 1000 ובעיגול למטה, נותן 1066.

מחבר הבעיה: Brian Dean