Problem
あなたはマネージャーとして働いており、来月の作業計画を作成します。各月は、T 個の等しい時間単位に分割されます。合計 n 個のタスクを実行する必要があります。ただし、すべてのタスクを 1 か月で完了することは不可能であることを理解しており、完了するタスクの一部を選択して最適な計画を立てたいと考えています。
各タスクについて、完了までに必要な時間 ti と利益 pi< がわかります。 /sub> は、完了したタスクが会社にもたらすものです。次のようなタスクを計画したいと考えています。
- 計画に含まれるタスクに費やした合計時間は
T を超えませんでした。
- これらのタスクから得られる利益の合計は最大でした。
上記の特性を持つ計画を立て、この計画の実行から生じる利益を決定します。
条件に一致する唯一のプランにタスクが含まれていない可能性があることに注意してください。
入力データ
最初の行には、自然数 T (1 ≤ T ≤ 100 000) と n (1 ≤ n &le) が含まれています; 10) - 1 か月あたりの時間単位の数とタスクの数。
次の n 行には、それぞれ ti と pi という 2 つの自然数が含まれています。 < /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 |