Maximum Profit with K Transactions

Given a list of stock prices and an integer \(k\) representing the maximum number of transactions allowed, compute the maximum profit achievable by performing at most \(k\) transactions. A transaction is defined as buying one stock and then selling it later. Note that you cannot perform multiple transactions simultaneously, meaning you must sell before buying again.

Note: A transaction is composed of a buy and a sell operation. When \(k\) is large enough (i.e. \(k > \frac{n}{2}\)), the problem turns into finding the maximum profit with an unlimited number of transactions, which can be computed by:

[ \text{Profit} = \sum_{i=1}^{n-1} \max(0, \text{prices}[i] - \text{prices}[i-1]) ]

Use dynamic programming to solve the problem efficiently.

inputFormat

The first line contains an integer \(T\), the number of test cases. For each test case:

• The first line contains two integers: \(k\) (the maximum number of transactions allowed) and \(n\) (the number of days).
• The second line contains \(n\) space-separated integers representing the stock prices for each day.

outputFormat

For each test case, output a single line containing the maximum profit achievable.

## sample

1
2 6
3 2 6 5 0 3

7

</p>