An Amazon fulfillment center has
The reward for processing order
The manager wants to process exactly
However, due to packing restrictions, no two selected orders can be adjacent in the original line.
Your task is to find the maximum total reward possible by selecting exactly
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of orders and the number of orders to select.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the reward of each order.
Print a single integer — the maximum total reward possible by selecting exactly KaTeX can only parse string typed expression non-adjacent orders.
Input
6 2
5 1 9 10 6 215Select orders KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. Their rewards are KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, giving total reward KaTeX can only parse string typed expression.
A better choice is to select orders KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. Their rewards are KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, giving total reward KaTeX can only parse string typed expression.
Orders KaTeX can only parse string typed expression and KaTeX can only parse string typed expression cannot both be selected because they are adjacent.
Example 2:
Input
5 3
4 7 2 9 511To select exactly KaTeX can only parse string typed expression non-adjacent orders from KaTeX can only parse string typed expression orders, the only possible positions are KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression. The total reward is KaTeX can only parse string typed expression.
Example 3:
Input
1 1
100100There is only one order, so it must be selected.