Why does my solution TLE on the last test case?

The answer space is monotonic, so binary search on it. Be careful with the loop condition (lo < hi vs lo <= hi) and how you move the bounds.