77 . 能量巡航
Description
宇宙船要沿著一條長度為 $n$ 的航線前進，每一天都要選擇一種行動，共有三種行動：
第一種：維持航行，能量不變
第二種：進行小幅加速，消耗 $1$ 點能量，並得到 $a_i$ 分
第三種：進行大幅加速，消耗 $2$ 點能量，並得到 $b_i$ 分
但宇宙船的引擎很不穩定，不能連續兩天都使用第三種行動。
一開始宇宙船有 $m$ 點能量。
請你計算在第 $1$ 天到第 $n$ 天中，合法安排行動後，最多可以得到多少分。
對於所有測試資料：
$1 \le n \le 5000$
$0 \le m \le 5000$
$0 \le a_i,\ b_i \le 10$$9$
Input Format
共輸入三行，
第一行輸入三個數字 $n,\ m$，
第二行輸入 $n$ 個數字，第 $i$ 個數字為 $a_i$，
第三行輸入 $n$ 個數字，第 $i$ 個數字為 $b_i$。
Output Format
輸出一個數字代表答案。
Sample Input 1
5 0 2 3 3 8 1 10 1 0 10 9
Sample Output 1
0
Sample Input 2
5 5 2 5 1 1 5 7 5 8 7 2
Sample Output 2
20
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測試資料 | 0 |
| 2 | 0~11 | $n \le 15$ | 25 |
| 3 | 0~21 | $n \le 100$ | 35 |
| 4 | 0~31 | 無額外限制 | 40 |