DA-F94-CA3

Time Limit: 2 Seconds    Memory Limit: 131072 KB

شرکت الگوریتم گستر شرق در زمینه تولید چوب شور فعالیت میکند. از آنجا که چند سالی است که محصولات این شرکت خوب فروش نمیرود، مسئولان آن در صدد برآمدند تا با یک نظر سنجی از مردم، سلیقه آنها را در باب چوب شور جویا شده و محصولی جدید عرضه کنند. برای همین آنها n نظر سنجی متفاوت تدارک دیده اند که میخواهند هرکدام را به فقط 1 نفر بدهند. با این حال آقای شوریده مسئول مارکتینگ شرکت اعتقاد دارد که آنها باید نظر افراد با خصوصیات مختلف را بسنجند تا بتوانند به نتیجه درست برسند. به همین دلیل، آنها تعدادی سوال "بله-خیر" آماده کرده اند که قبل از نظرسنجی، از سوال اول شروع کرده و آن را از فرد مورد نظر میپرسند و با توجه به جواب فرد به سوال، یا سوالی دیگر و یا در نهایت یک نظر سنجی به او می دهند.این عمل سوال پرسیدن تا زمانی که به یک نظر سنجی ختم نشود، ادامه پیدا می کند. همچنین، آقای شوریده با توجه به میزان اهمیت هر نظرسنجی، عددی را به آن نظرسنجی نسبت داده است.(طبیعتا عدد بزرگتر معادل اهمیت بیشتر است.) هر نظر سنجی دارای تعدادی سوال است که تخمین زده شده پاسخ به هرکدام از آنها 1 دقیقه طول خواهد کشید. همچنین، هرسوال بله-خیر هم 1 دقیقه طول میکشد. بنابراین، یک نظر سنجی با x سوال ،که قبل از آن y سوال بله-خیر از پرسیده شده باشد، x+y دقیقه از زمان فرد موردنظر را خواهد گرفت. از آنجا که افرادی که چوب شور میخورند بسیار افراد درگیری هستند، آقای شوریده نمیخواهد بیشتر از T دقیقه از وقت آن ها را بگیرد. به همین دلیل از شما میخواهد تا سوالات و نظرسنجی هارا به ترتیبی قرار دهید که نظرسنجی هایی که میتواند پرسیده شود، دارای مجموع اهمیت بیشینه باشد. برای فهم بیشتر به این مثال ها توجه کنید: الف)5 نظرسنجی داریم که همه آنها 4 سوال دارند. و میزان اهمیت آنها هم 1 تا 5 است. همچنین T=5. بهترین جوابی که میتوانیم برگزینیم (بیشینه مجموع اهمیت ها) 9 است. برای درک این موضوع به این توجه کنید که اولا نمیتوان بیشتر از 1 سوال پرسید (زیرا در این صورت وقتی که از فرد مورد نظر گرفته میشود از T دقیقه بیشتر خواهد شد) و ثانیا اگر هم سوالی نپرسیم، حداکثر میتوان از 1 نفر نظرسنجی کرد که بهترین جواب در آن صورت 5 است.(با اهمیت‌ترین نظرسنجی) ب) 5 نظرسنجی داریم که به این صورت هستند: 4/4 3/3 2/2 1/1 1/1 که هر زوج عدد اهمیت و تعداد سوال هر نظر سنجی را مشخص میکند. در این مثال T = 5 است و همانطور که مشخص است هیچ فردی وجود ندارد که بیشتر از 5 دقیقه وقت گذاشته باشد.مثلا اگر فردی به نظر سنجی 2/2 پاسخ بدهد، 3 دقیقه برای سوال های 1 تا 3 و 2 دقیقه برای نظر سنجی زمان گذاشته که در مجموع 5 دقیقه می شود که از T کمتر است و مشکلی ندارد. برای درک اینکه چرا این جواب بهترین جواب است به این موضوع دقت کنید که ما درختی پیدا کردیم که توانستیم در آن تمام نظرسنجی‌ها را جا دهیم. و همچنین با جابه‌جایی نظرسنجی‌ها ، شرط سوال (کمتر از 5 دقیقه وقت بگیرد) را نقض خواهیم کرد.

Input

در خط اول به ترتیب اعداد n و T داده میشوند(n<=1000 و t<=100) و در n خط بعدی در هر خط دو عدد داده مشود که به ترتیب تعداد سوالات نظرسنجی اول (ti) و اهمیت آن (qi)است.( ti<=T و qi<=1000)

Output

خروجی تنها یک خط است که باید در آن جواب بهینه را چاپ کنید(ماکسیمم مجموع اهمیت نظرسنجی ها).

Sample Input

5 5
1 1
1 1
2 2
3 3
4 4

Sample Output

11

Submit