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