1231 . 寵物雞問題
TopCoder
Tags
Description
有一個電子寵物雞遊戲，遊戲軟體中會提供若干種食物，每種食物都有固定的熱量，並有其保存期限。從飼養電子寵物雞開始計時後，每分鐘內你可以從這些食物中選擇一種食物餵食寵物雞(一分鐘只能餵食一次，否則寵物雞會消化不良)，但要注意不可餵食保存期限過期的食物，否則寵物雞會立刻暴斃。餵食後食物數量會自動減少，且每單位熱量會使你的寵物雞體重增加1公斤；每達到1分鐘沒有餵食，寵物雞體重會減少1公斤。現在電子寵物雞公司為了促銷，特別辦了一個電子寵物雞飼養高手的比賽，給定一樣的食物種類、熱量、及保存期限，在比賽終止時間到達時，將其寵物雞的體重增加最多者將贏得冠軍。
請你寫出一個程式，由所給定的食物種類、熱量、保存期限，以及比賽終止時間，找出一定可贏得冠軍的飼養方法之體重增加量。
Input Format
輸入檔案第一行為N值（$N\leq 10^ 5$）, 表示有N種食物。第二行開始的N行，每行包含兩個正整數值，以空白區分，表示每種食物的熱量及保存期限。第i+1行中儲存的是第i種食物的熱量及保存期限。第N+2行為一個正整數值，表示比賽設定時間。
請注意！保存期限的值若為t，是指從飼養開始計時後超過t分鐘便算超過保存期限。而比賽終止時間的值若為k，是指從飼養開始計時後第k分鐘為比賽終止時間。
保證答案與給定的所有數字都在int範圍內。
Output Format
請輸出在到達比賽終止時間時，必定可贏得冠軍的體重增加量(以公斤為單位)。
Sample Input 1
10 1
100 2
30 2
15 2
27 1
200 3
3
Sample Output 1
Sample Input 2
100 1
80 1
50 2
90 2
70 3
4
Sample Output 2
Hints
範例一說明：
第一分鐘和第二分鐘分別餵食第二種(熱量100)和第三種食物(熱量30)，並在第三分鐘餵第六種食物(熱量200)，可使體重增加量達到最高330公斤。
範例二說明：
第一分鐘和第二分鐘分別餵食第一種(熱量100)和第四種食物(熱量90)，並在第三分鐘餵第五種食物(熱量70)，到第四分鐘沒食物可餵食減少1公斤，共使體重增加量達到最高259公斤。
Problem Source
原TIOJ1231 / TOI2005初選(prob 3)。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |