Problem
Yönetici olarak çalışıyorsunuz ve gelecek ay için bir çalışma planı hazırlıyorsunuz. Her ay eşit T zaman birimine bölünmüştür. Toplamda yapılması gereken n görev var. Ancak, tüm görevleri bir ayda tamamlamanın mümkün olmayabileceğini anlıyorsunuz ve bazılarını tamamlamayı seçerek en uygun planı yapmak istiyorsunuz.
Her görev için ti ti kârını ve pi< kârını biliyoruz /sub> tamamlanan görevin şirkete getireceği. Bazı görevleri şu şekilde planlamak istiyorsunuz:
- Planda yer alan görevler için harcanan toplam süre
T'yi geçmedi.
- Bu görevlerden elde edilen toplam kâr maksimumdu.
Yukarıda açıklanan özelliklere sahip bir plan yapın ve bu planın uygulanmasından elde edilecek karı belirleyin.
Koşullarla eşleşen tek planın herhangi bir görev içermeyebileceğini lütfen unutmayın.
Giriş verileri
İlk satır T (1 ≤ T ≤ 100 000) ve n (1 ≤ n &le) doğal sayılarını içerir ; 10) - aylık zaman birimi sayısı ve görev sayısı.
Aşağıdaki n satırları, her biri ti ve pi olmak üzere iki doğal sayı içerir. (1 <= ti, pi <= 100 000) - harcanacak zaman i'inci görevi tamamlayın ve onu tamamlayarak elde edilebilecek kârı elde edin.
Künye verileri
Tek bir sayı yazdır — yukarıda yazılı koşulları sağlayan bir plan hazırlayarak elde edilebilecek maksimum kâr.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |