Problem
شما به عنوان مدیر کار می کنید و یک برنامه کاری برای ماه آینده تهیه می کنید. هر ماه به T واحدهای مساوی زمان تقسیم می شود. در مجموع وظایف n وجود دارد که باید انجام شوند. با این حال، می‌دانید که ممکن است انجام همه کارها در یک ماه ممکن نباشد و می‌خواهید با انتخاب برخی از آنها برای تکمیل، برنامه‌ای بهینه داشته باشید.
برای هر کار، ما زمان ti را که باید برای تکمیل آن صرف کنیم و همچنین سود pi< می دانیم /sub> که کار تکمیل شده برای شرکت به ارمغان می آورد. می‌خواهید چند کار را طوری برنامه‌ریزی کنید که:
- کل زمان صرف شده برای کارهای گنجانده شده در طرح از
T تجاوز نکرده است.
- کل سود حاصل از این کارها حداکثر بود.
طرحی تهیه کنید که دارای خواصی باشد که در بالا توضیح داده شد و سود حاصل از اجرای این طرح را مشخص کنید.
لطفاً توجه داشته باشید که تنها طرحی که با شرایط مطابقت دارد ممکن است حاوی هیچ کار نباشد.
داده‌های ورودی
خط اول شامل اعداد طبیعی T (1 ≤ T ≤ 100 000) و n (1 ≤ n &le است. ؛ 10) - تعداد واحدهای زمانی در ماه و تعداد کارها.
خطوط n زیر حاوی دو عدد طبیعی هستند که هر کدام ti و pi < /code> (1 <= ti, pi <= 100 000) - زمان صرف برای iامین کار و سودی که با تکمیل آن بدست می آید را تکمیل کنید.
داده‌های چاپی
چاپ یک عدد — حداکثر سودی که می توان با تهیه طرحی به دست آورد که شرایط نوشته شده در بالا را برآورده کند.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |