Complexity Analysis

Each element is pushed to the heap at most twice: once for itself, once for slope adjustment after popping. Each push and pop operation is $O(\log n)$. Total operations: $O(n)$ pushes and $O(n)$ pops in the worst case.

Time complexity: $O(n \log n)$. Space complexity: $O(n)$ for the heap storing all breakpoints. Compare to naive DP: $O(n \cdot V^2)$ with $V = 10^9$ means $10^{18}$ operations. Impossible. Slope Trick reduces this to $O(n \log n)$, making previously impossible problems solvable in milliseconds.