Maximum stock trading profit with at most k buy-and-sell transactions

You are given an integer `k` and a list `prices`, where `prices[i]` is the price of one share of a stock on day `i`. You may complete at most `k` transactions, where a transaction means buying one share and later selling it. Return the maximum total profit you can achieve. ### Function Signature ```python def max_profit_k_transactions(k: int, prices: List[int]) -> int: ``` ### Rules - You can hold at most one share at a time, so you must sell before buying again. - A sale and the next purchase may happen on the same day. - Any number of transactions from zero up to `k` is allowed; if no trade makes money, return `0`. - `k` may exceed the number of profitable trades available; the extra allowance simply goes unused. ### Constraints - `1 <= k <= 100` - `1 <= len(prices) <= 1000` - `0 <= prices[i] <= 1000` ### Examples Example 1 ```text Input: k = 2, prices = [3, 8, 2, 6, 1, 9] Output: 13 ``` Buy at 3 and sell at 8 for 5, then buy at 1 and sell at 9 for 8. Pairing the rise from 2 to 6 with either of the others earns less. Example 2 ```text Input: k = 3, prices = [3, 8, 2, 6, 1, 9] Output: 17 ``` With a third transaction allowed, all three rises can be taken: 5 + 4 + 8. Example 3 ```text Input: k = 1, prices = [4, 2, 7, 1, 3] Output: 5 ``` The single best trade buys at 2 and sells at 7.