/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は、商店街の街路灯の管理を任されています。商店街には N 個の街路灯が一直線に並んでおり、左から順に街路灯 1, 街路灯 2, \ldots, 街路灯 N と番号が付けられています。街路灯は直線状に配置されており、街路灯 N と街路灯 1 は隣接していません。高橋君は、これらの街路灯の一部を LED 照明に交換することを検討しています。
街路灯 i (1 \leq i \leq N) を LED に交換すると、年間の電気代削減効果は V_i 円であり、交換にかかる費用は W_i 円です。各街路灯について、LED に交換するかしないかのいずれかを選びます（同じ街路灯を複数回交換することはありません）。高橋君に与えられた交換費用の予算の上限は K 円であり、LED に交換する街路灯の交換費用の合計が K 円以下でなければなりません。
ところが、この商店街には古い電気配線の制約があります。番号が連続する隣り合う 2 つの街路灯をともに LED にすると、配線の容量を超えてブレーカーが落ちてしまいます。すなわち、すべての i (1 \leq i \leq N-1) について、街路灯 i と街路灯 i + 1 の両方を LED に交換することは許されません。
高橋君が、予算の制約と配線の制約の両方を満たすように LED に交換する街路灯を選ぶとき、年間の電気代削減効果の合計の最大値を求めてください。なお、1 つも交換しないという選択も許されます。その場合、削減効果の合計は 0 円です。
制約
- 1 \leq N \leq 200
- 1 \leq K \leq 10^4
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K V_1 W_1 V_2 W_2 \vdots V_N W_N
- 1 行目には、街路灯の個数を表す整数 N と、交換費用の予算の上限を表す整数 K（単位は円）が、スペース区切りで与えられる。
- 続く N 行のうち i 行目 (1 \leq i \leq N) には、街路灯 i の年間電気代削減効果 V_i（単位は円）と交換費用 W_i（単位は円）が、スペース区切りで与えられる。
出力
年間の電気代削減効果の合計の最大値を整数として 1 行で出力してください。
入力例 1
4 5 100 3 200 2 150 3 80 2
出力例 1
280
入力例 2
6 10 500 4 300 3 400 5 600 4 200 2 350 3
出力例 2
1250
入力例 3
10 50 1000000000 8 500000000 12 800000000 10 300000000 5 900000000 15 700000000 9 400000000 7 600000000 11 250000000 6 450000000 8
出力例 3
3550000000
Score : 400 pts
Problem Statement
Takahashi is in charge of managing the street lights of a shopping district. The shopping district has N street lights arranged in a straight line, numbered from left to right as street light 1, street light 2, \ldots, street light N. The street lights are placed along a line, and street light N and street light 1 are not adjacent. Takahashi is considering replacing some of these street lights with LED lighting.
If street light i (1 \leq i \leq N) is replaced with LED, the annual electricity cost reduction is V_i yen, and the replacement cost is W_i yen. For each street light, you choose either to replace it with LED or not (no street light is replaced more than once). The budget limit given to Takahashi for replacement costs is K yen, so the total replacement cost of the street lights replaced with LED must be at most K yen.
However, there is an old electrical wiring constraint in this shopping district. If two consecutively numbered adjacent street lights are both replaced with LED, the wiring capacity will be exceeded and the breaker will trip. That is, for all i (1 \leq i \leq N-1), it is not allowed to replace both street light i and street light i + 1 with LED.
Find the maximum total annual electricity cost reduction when Takahashi selects which street lights to replace with LED while satisfying both the budget constraint and the wiring constraint. Note that choosing to replace none of the street lights is also allowed. In that case, the total reduction is 0 yen.
Constraints
- 1 \leq N \leq 200
- 1 \leq K \leq 10^4
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq W_i \leq 10^4 (1 \leq i \leq N)
- All inputs are integers
Input
N K V_1 W_1 V_2 W_2 \vdots V_N W_N
- The first line contains an integer N representing the number of street lights and an integer K representing the budget limit for replacement costs (in yen), separated by a space.
- The i-th line (1 \leq i \leq N) of the following N lines contains the annual electricity cost reduction V_i (in yen) and the replacement cost W_i (in yen) for street light i, separated by a space.
Output
Output the maximum total annual electricity cost reduction as an integer on a single line.
Sample Input 1
4 5 100 3 200 2 150 3 80 2
Sample Output 1
280
Sample Input 2
6 10 500 4 300 3 400 5 600 4 200 2 350 3
Sample Output 2
1250
Sample Input 3
10 50 1000000000 8 500000000 12 800000000 10 300000000 5 900000000 15 700000000 9 400000000 7 600000000 11 250000000 6 450000000 8
Sample Output 3
3550000000