I don’t understand the correctness proof of the book’s algorithm.

Especially for the sentence “Therefore, a must be assigned to a* at some iteration. At this point, b <= b* since A[a* - 1, b - 1] satisfies the sum constraint”.

How can we guarantee A[a* - 1, b - 1] <= k? And where does A[a* - 1, b - 1] come from?

Can anyone elaborate the proof in more details?

Thanks in advance.