Как доказать правильность этого алгоритма?

Дано две последовательности размера n a и b, известно что a_{i - 1} < a_i. Нужно выбрать последовательность индексов максимального размера c такую что для каждого элемента i выполняется sum_{j=1}^{i} b_{c_j} \leq a_{c_i}.

Утверждается что получить c можно постепенно изменяя текущий ответ посредством использования i-го элемента в порядке возрастания i.
Если мы можем добавить текущий элемент i в конец последовательности c так чтобы выполнялось sum_{j=1}^{|c|} b_{c_j} + b_i \leq a_i, то мы добавляем этот элемент в конец.
Иначе если max_{j = 1}^{|c|}(b_{c_j}) > b_i, мы удаляем один элемент k из c при котором b_{c_k} = max_{j = 1}^{|c|}(b_{c_j}), и добавляем элемент i.

Как доказать что следуя вышеописанному алгоритму мы в итоге получим c которая соответствует требованиям из первого абзаца?

c это подпоследовательность a или b?

заредачил

© 2021-2022 Общественный Фонд «Beyond Curriculum» (CC BY-NC-SA 4.0 International)