Единственное отличие между простой и сложной версиями — то, что вам необходимо завершить все проекты в легкой версии, но это не обязательно в сложной версии.

Поликарп — очень известный фрилансер. Его текущий рейтинг равен $$$r$$$.

Некоторые очень богатые заказчики попросили его завершить некоторые проекты для их компаний. Чтобы завершить $$$i$$$-й проект, Поликарпу необходимо иметь хотя бы $$$a_i$$$ единиц рейтинга; после того, как он завершит этот проект, его рейтинг изменится на $$$b_i$$$ (его рейтинг увеличится или уменьшится на $$$b_i$$$) ($$$b_i$$$ может быть положительным и отрицательным). Рейтинг Поликарпа не может падать ниже нуля, потому что люди перестанут доверять фрилансеру с таким низким рейтингом.

Поликарп может выбрать порядок, в котором он выполняет проекты. Более того, он даже может пропускать некоторые из проектов.

Чтобы получить больше опыта (и денег, конечно же), Поликарп хочет выбрать подмножество проектов, имеющее максимально возможный размер, и порядок, в котором он будет их выполнять, чтобы он имел достаточный рейтинг перед началом каждого проекта и неотрицательный рейтинг после окончания каждого проекта.

Ваша задача — посчитать максимально возможный размер такого подмножества проектов.