AT_past202309_h 休暇

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.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ \ldots $ $ A_N $

Print the answer.

### Sample Explanation 1 You can play on days $ 1 $ , $ 3 $ , and $ 5 $ , and study on days $ 2 $ and $ 4 $ to get a joy of $ 12 $ . ### Sample Explanation 2 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. ### 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.