/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
問題文
あなたは明日からの N 日間の休暇の予定を立てようとしています。
それぞれの日には「遊ぶ」「宿題をする」のどちらかを行います。
N 日間のうち M 日以上宿題をする日がある必要があります。
2 日以上連続で宿題をすることはしません。
i 日目に遊ぶと、楽しさ を A_i 得ます。宿題をするとその日の楽しさは 0 です。
N 日間で得られる楽しさの合計の最大値を求めてください。
制約
- 1 \leq N \leq 3000
- 0 \leq M \leq \frac{N+1}{2}
- 1 \leq A_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 2 3 2 4 1 5
出力例 1
12
1,3,5 日目に遊び、2,4 日目に宿題をすることで、楽しさ 12 を得ます。
入力例 2
5 2 3 5 4 1 2
出力例 2
11
2,3,5 日目に遊び、1,4 日目に宿題をすることで、楽しさ 11 を得ます。
2 日以上連続して宿題をすることはできないことに注意してください。
入力例 3
10 0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
10000000000
Problem Statement
You are making plans for an upcoming N-day vacation.
On each day, you will either "play" or "study."
Among the N days, you need to study on at least M days.
You will not study on two or more days in a row.
If you play on day i, you get a joy of A_i; if you study, the joy is 0 on that day.
Find the maximum possible total joy of the N days.
Constraints
- 1 \leq N \leq 3000
- 0 \leq M \leq \frac{N+1}{2}
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
5 2 3 2 4 1 5
Sample Output 1
12
You can play on days 1, 3, and 5, and study on days 2 and 4 to get a joy of 12.
Sample Input 2
5 2 3 5 4 1 2
Sample Output 2
11
You can play on days 2, 3, and 5, and study on days 1 and 4 to get a joy of 11.
Note that you cannot study on two or more days in a row.
Sample Input 3
10 0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
10000000000