Implementation Checklist

Checklist $1$: Verify convexity. Test small cases manually. If $g$($k$) isn't convex, the trick fails. Checklist $2$: Handle lambda precision. Use integer arithmetic if possible. Binary search on integers is cleaner. Checklist $3$: Track count correctly. Pair (cost, count) comparisons must be consistent. Checklist $4$: Final answer. After finding optimal lambda, compute actual answer: $cost - K \cdot \lambda$. Test on small inputs where you can verify the answer manually. Check that the count varies correctly with penalty.

Time complexity: $O(n \log C)$ where $C$ is the penalty search range, times the cost of the inner DP.

Space complexity: $O(n)$ for the DP arrays.