Problem
Anda bekerja sebagai pengurus dan merangka rancangan kerja untuk bulan berikutnya. Setiap bulan dibahagikan kepada T unit masa yang sama. Terdapat tugasan n secara keseluruhan yang perlu dilakukan. Walau bagaimanapun, anda faham bahawa anda mungkin tidak dapat menyelesaikan semua tugasan dalam sebulan dan anda ingin membuat rancangan yang optimum dengan memilih beberapa tugasan untuk diselesaikan.
Untuk setiap tugasan, kita tahu masa ti yang perlu diluangkan untuk menyelesaikannya, serta keuntungan pi< /sub> yang tugas yang telah selesai akan dibawa kepada syarikat. Anda ingin merancang beberapa tugas supaya:
- Jumlah masa yang dibelanjakan untuk tugasan yang disertakan dalam rancangan tidak melebihi
T.
- Jumlah keuntungan daripada tugasan ini adalah maksimum.
Buat pelan yang mempunyai hartanah yang diterangkan di atas dan tentukan keuntungan yang terhasil daripada pelaksanaan pelan ini.
Sila ambil perhatian bahawa satu-satunya pelan yang sepadan dengan syarat mungkin tidak mengandungi sebarang tugas.
Input Data
Baris pertama mengandungi nombor asli T (1 ≤ T ≤ 100 000) dan n (1 ≤ n &le ; 10) - bilangan unit masa sebulan dan bilangan tugasan.
Barisan n berikut mengandungi dua nombor asli setiap satu ti dan pi < /code> (1 <= ti, pi <= 100 000) - masa untuk meluangkan selesaikan tugasan idan keuntungan yang boleh diperolehi dengan menyelesaikannya.
Cetak data
Cetak satu nombor — keuntungan maksimum yang boleh diperolehi dengan merangka pelan yang memenuhi syarat yang dinyatakan di atas.
Contoh
| # |
Input |
Output |
| 1 |
10 3
8 100
3 10
3 10
| 100 |
| 2 |
10 4
5 10
5 20
25
26 |
31 |