题目描述

小蓝正在研究股票市场，他希望从股票交易中获得最大利润。

给定一个长度为 $N$ 的整数数组 $A_{1}, A_{2}, \cdots, A_{N}$，其中 $A_i$ 表示一支股票在第 $i$ 天的价格，以及一个整数 $k$，表示最多可以进行的交易笔数。

小蓝可以进行最多 $k$ 笔交易，每笔交易可以是以下任一类型：

1. 普通交易：在第 $i$ 天买入，然后在之后的第 $j$ 天卖出，其中 $i < j$。你的利润是 $A_j - A_i$。
2. 做空交易：在第 $i$ 天卖出，然后在之后的第 $j$ 天买回，其中 $i < j$。你的利润是 $A_i - A_j$。

注意：

• 小蓝不能同时参与多笔交易（他必须在再次购买前出售掉之前的股票）。
• 每天只能进行一次操作（买入、卖出或不做任何操作）。

请你帮助小蓝计算他能获得的最大利润。

输入描述

第一行包含两个整数 $N$ 和 $k$，分别代表数组长度和最多交易次数。

第二行包含 $N$ 个整数 $A_1, A_2, \cdots, A_N$，其中 $A_i$ 表示股票在第 $i$ 天的价格。

输出描述

输出一行包含一个整数表示最大利润。

样例

5 2
2 4 1 5 3

6

样例解释：

样例解释： 一种可能的最优策略：

第1天买入(价格=2)，第2天卖出(价格=4)，利润为2 第3天买入(价格=1)，第4天卖出(价格=5)，利润为4 总利润为6

数据范围

对于所有评测用例，$1 \leq N \leq 10^{3}$，$1 \leq k \leq 100$，$0 \leq A_i \leq 10^{5}$。