Maximum Stock Profit with Limited Transactions

You are given a list of stock prices over N days and an integer K representing the maximum number of transactions allowed. A transaction consists of buying and then selling one share of the stock. Your task is to compute the maximum profit achievable with at most K transactions.

If it is better to perform as many transactions as possible, note that performing a transaction is only profitable when the price difference is positive. In fact, when K is large enough (specifically, when K \geq N/2), the problem reduces to summing all positive differences.

For the bounded case, a dynamic programming approach is typically used. One useful recurrence is:

$$dp[k][i] = \max(dp[k][i-1], \; prices[i] + maxDiff) $$

where maxDiff is updated as:

$$maxDiff = \max(maxDiff, dp[k-1][i] - prices[i])$$

Compute and output the maximum profit possible under these conditions.

inputFormat

The input is read from stdin in the following format:

N
price1 price2 ... priceN
K

Here, N is the number of days (an integer), the second line contains N space-separated integers representing the stock prices, and the third line contains an integer K which is the maximum number of transactions allowed.

outputFormat

The output is a single integer representing the maximum profit that can be achieved and should be printed to stdout.

## sample

7
3 2 6 5 0 3 2
2

7