мы стартуем с i = 0 и j = M-1. Пусть ближайшее решение находится в индексах i0, j0
рассмотрим возможные состояния:
1) мы уже в (i0, j0), решение найдено
2) мы в (i0, b), где b > j0. Здесь сумма больше чем С, мы просто уменьшаем j до j0 и приходим в п.1
3) мы в (a, j0), где a < i0. Сумма меньше С, увеличиваем i до i0, приходим в п1
4) мы в (a, b), где a < i0 и b > j0. Поскольку i может только увеличиваться, а j - только уменьшаться, то выйдем на п.2 или п.3, а оттуда на п.1
Поскольку стартовали мы гарантированно из состояния 1...4, то все прочие состояния невозможна, потому что кейсы 1...4 уводят на п.1
Вывод: мы не проскочим решение (i0, j0).
ps: для наглядности можно разместить все точки (i, j) на координатной плоскости и заметить, что (i0, j0) - не просто точка, которую можно "обойти": она задает прямоугольник, в котором мы находимся на старте и из которого мы не выйдем, перепрыгнув через сторону.
