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