Maximum Value of K Coins From Piles

Treat each pile as a group

You may take only top coins, so precompute each pile's prefix sums. Let dp[c] be the greatest value after processing some piles and taking exactly c coins. For the next pile, build a fresh row: for every target c, try taking t top coins from that pile, where 0 <= t <= min(c, pileSize), and combine old[c-t] + prefix[t]. The fresh row prevents taking from the same pile more than once in one stage.

Complexity and correctness

The state is exact, so do not initialize unreachable states to zero if coin values could be negative; use negative infinity except dp[0]=0. The final answer is dp[k]. If total pile sizes are n, the standard nested transition is O(nk) time and O(k) space, because each feasible prefix is considered once per relevant target. Test k=0, one pile, and a request larger than the number of available coins. Explain that arbitrary subsets of a pile are illegal because accessibility is prefix-only.