Implement max profit with K transactions (DP)

Given an array prices[0..n-1] of daily stock prices and an integer k, implement a bottom-up dynamic program to compute the maximum achievable profit with at most k buy-sell transactions (no overlapping positions). Requirements: (1) Return both the profit and the list of (buy_day, sell_day) pairs achieving it; break ties by lexicographically smallest sequence of pairs. (2) Time: O(nk), Space: O(k). (3) Handle edge cases k = 0, n < 2, and prices with plateaus. (4) Prove correctness via optimal substructure and explain how you avoid O(n^2 k).