TopCoder

Thumb fhvirus
FHVirus
$\huge{WHP}$

User's AC Ratio

92.3% (12/13)

Submission's AC Ratio

43.9% (25/57)

Description

自從時光之初,你便被交付了N項任務要去完成。
且一開始時,你的銀行帳戶中總共有C元,且總共有P單位的體力。

但每件任務雖然完成後會有獎賞,但也會消耗你的體力。甚且有些任務在執行時需要一些支出。
只要你入不敷出(也就是該任務需要的錢比你銀行中的錢還多),一切遊戲就宣告結束。
經過審慎的評估,你決定選擇某些(也可以是全部)任務來執行,使得在你選擇的任務完成後,銀行帳戶中擁有的錢最多。

不過一旦你體力小於等於0,就會立刻死掉。當然,你任何一個時刻都不能死掉。

Input Format

輸入的第一行依序有三個正整數N, C, P,
接下來有N行,第i行依序有三個非負整數ci、ai、pi (但pi為正),代表這個任務執行時需要支出ci元,
任務執行完後會獲得ai元,而執行後則會消耗你pi單位的體力。

Output Format

輸出一行,包含一個正整數A,代表你銀行的帳戶最後最多可以有幾元。

Sample Input

3 5 3
6 7 1
4 6 1
3 5 100

Sample Output

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10