Description

Doraemon aims to make a fortune from the significant daily price changes of dorayakis. He plans to buy a dorayaki on one day and sell it on another to profit from the price spread. To keep his plan secret, Doraemon will only hold one dorayaki at a time, meaning he must sell each one before buying another.

Given the dorayaki prices over a continuous span of N days, please calculate the maximum profit Doraemon can gain.

(This part differs from the Practice Problem "Doraemon's dorayaki")
Recently, Doraemon decided not to be too ostentatious (炫耀的) for this evil plan and chose to limit the number of transactions he can make (where a 'transaction' is defined as buying and selling one dorayaki). In this problem, an integer M is given to restrict Doraemon to do at most M transactions. If M equals -1, this means that there is still no limit to the number of transactions.

 

Sample I/O Explanation

N = 8 days, M = unlimited transactions (-1), prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 2 (-2) -> Sell on day 4 (+6) -> Buy on day 5 (-3) -> Sell on day 6 (+8) -> Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-2) + 6 + (-3) + 8 + (-1) + 9 = 17

N = 8 days, M = 1 transaction, prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-1) + 9 = 8

N = 8 days, M = 2 transactions, prices = [7, 2, 5, 6, 3, 8, 1, 9]
Buy on day 2 (-2) -> Sell on day 6 (+8) -> Buy on day 7 (-1) -> Sell on day 8 (+9)
Maximum profit = (-2) + 8 + (-1) + 9 = 14

 

Input

• The first line contains two integers N, M (1 ≤ N ≤ 10⁷, M ∈ {-1, 1, 2}), representing the number of days and the limited number of transactions.
• The second line contains N integers: x₁, x₂, ..., x_N (1 ≤ x_i ≤ 10⁹), where x_i represents the price of dorayakis on the i-th day.

 

Output

Output a single line containing one integer — the maximum profit Doraemon can gain.

---

Constraints

• Test Case 1 : N ≤ 20, M = -1
• Test Case 2 : N ≤ 20, M = 1
• Test Cases 3 ~ 4 : N ≤ 10⁵, M = -1
• Test Case 5 : N ≤ 10⁵, M = 1
• Test Case 6 : N ≤ 10⁵, M = 2
• Test Case 7 : N ≤ 10⁷, M = 1
• Test Case 8 : N ≤ 10⁷, M = 2

Hints

• N ≤ 20: Brute-Force Recursion or Loop
• N ≤ 10⁵: Recursion and Memorization
• N ≤ 10⁷: Be aware of memory space limitation (128 MB), and try to observe the characteristics of the problem and use an approach other than recursion

---

 

Sample Input  Download

Sample Output  Download

Tags

Discuss