1675 . 可能的任務
TopCoder
Tags
Description
自從時光之初，你便被交付了N項任務要去完成。
且一開始時，你的銀行帳戶中總共有C元，且總共有P單位的體力。
但每件任務雖然完成後會有獎賞，但也會消耗你的體力。甚且有些任務在執行時需要一些支出。
只要你入不敷出(也就是該任務需要的錢比你銀行中的錢還多)，一切遊戲就宣告結束。
經過審慎的評估，你決定選擇某些(也可以是全部)任務來執行，使得在你選擇的任務完成後，銀行帳戶中擁有的錢最多。
不過一旦你體力小於等於0，就會立刻死掉。當然，你任何一個時刻都不能死掉。
Input Format
輸入的第一行依序有三個正整數N, C, P，
接下來有N行，第i行依序有三個非負整數ci、ai、pi (但pi為正)，代表這個任務執行時需要支出ci元，
任務執行完後會獲得ai元，而執行後則會消耗你pi單位的體力。
Output Format
輸出一行，包含一個正整數A，代表你銀行的帳戶最後最多可以有幾元。
Sample Input 1
3 5 3
6 7 1
4 6 1
3 5 100
6 7 1
4 6 1
3 5 100
Sample Output 1
8
Hints
對於所有的測資，1≦N, P≦5,000，且0≦C, ci, ai≦20,000。
Problem Source
原TIOJ1675 / 建國中學99年校內培訓contest #4 prob 4
problem setter:suhorng
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |