683. Best Time to Buy and Sell Stock - IV

0

Hard

Given an array **prices** representing the stock prices on each day, and an integer **k**, find the **maximum profit** that can be achieved by completing at most k transactions. Note that multiple transactions cannot be done simultaneously (i.e., the stock must be sold before buying again).

Input Format

The first line contains two space-separated integers n (the size of the array) and k. The second line contains an integer array prices.

Output Format

Print the maximum profit that can be achieved.

Example

Input

6 2
3 2 6 5 0 3

Output

7

Constraints

1 <= k <= 100

1 <= prices.length <= 1000

0 <= prices[i] <= 1000

1 <= prices.length <= 1000

0 <= prices[i] <= 1000

Loading...

View Submissions

Console