FJ נכנס לעסקי חפצי נוי, וקונה ומוכר דברים קטנים כגון קישוטי עץ חג המולד בצורת פרות. הוא יודע שימכור כל פריט שיוכל לרכוש מקטלוג של $N$ ($1 \le N \le 100$) סוגי חפצי נוי של פרות, ויכול לקנות מכל סוג כמה שירצה. יש לו רק $M$ ($1 \le M \le 100,000$) כסף להשקעה, אך הוא רוצה למקסם את הרווח (שמוגדר באופן מעט חריג) בסוף שנת העסקים הראשונה.

פריט מסוג $i$ עולה $C_i$ ($1 \le C_i \le 100,000$) ומניב הכנסה $R_i$ ($1 \le R_i \le 100,000$) לכל פריט שנמכר (רווח $R_i-C_i$). FJ יכול לשלב את הפריטים הנמכרים כרצונו. אין צורך להוציא את כל כספו בקנייה.

מהו הרווח הכולל המרבי ($profit = initial\_cash - all\_costs + all\_sales$) בסוף השנה הראשונה? מובטח שהוא קטן מ־$1,000,000,000$.

התבוננו במקרה עם $3$ סוגים בלבד וסכום התחלתי $M=17$. העלות וההכנסה מכל סוג הן:

             חפץ נוי     עלות     הכנסה
               #        C_i       R_i
               1         2         4
               2         5         6
               3         3         7

FJ צריך לקנות $5$ פריטים מסוג $3$ תמורת $15$, ועוד $1$ מסוג $1$ תמורת $2$, בסך הכול $17$. הרווח יהיה $5 * (7-3) + 1 * (4-2) = 5*4 + 1*2 = 22$. עם מבנה העלויות וההכנסות הזה אין אפשרות לשפר.

הערה: מקרה הבדיקה השני מאתגר, אך התשובה שלנו נכונה.

קלט

• שורה 1: שני מספרים שלמים המופרדים ברווח: $N$ ו־$M$.

• שורות $2..N+1$: שורה $i+1$ מכילה שני מספרים שלמים המופרדים ברווח: $C_i$ ו־$R_i$.

פלט

• שורה 1: הרווח המרבי ש־FJ יכול להפיק עם העלויות וההכנסות הנתונות.

דוגמאות

קלט 1

3 17
2 4
5 6
3 7

פלט 1

22

מקור הבעיה: בעיה מסורתית, 2009.