دخل 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.