TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

85.7% (42/49)

Submission's AC Ratio

27.2% (77/283)

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

Sample Input #1:

6
10 1
100 2
30 2
15 2
27 1
200 3
3

Sample Input #2:

5
100 1
80 1
50 2
90 2
70 3
4

Sample Output

Sample Output #1:

330

Sample Output #2:

259

Hints

範例一說明:
第一分鐘和第二分鐘分別餵食第二種(熱量100)和第三種食物(熱量30),並在第三分鐘餵第六種食物(熱量200),可使體重增加量達到最高330公斤。
範例二說明:
第一分鐘和第二分鐘分別餵食第一種(熱量100)和第四種食物(熱量90),並在第三分鐘餵第五種食物(熱量70),到第四分鐘沒食物可餵食減少1公斤,共使體重增加量達到最高259公斤。

Problem Source

原TIOJ1231 / TOI2005初選(prob 3)。

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 2000 65536 262144
2 2000 65536 262144
3 2000 65536 262144
4 2000 65536 262144
5 2000 65536 262144