В 2013-м году авторский коллектив Берляндского государственного университета должен подготовить задачи к n олимпиадам. Будем считать, что олимпиады пронумерованы последовательными целыми числами от 1 до n. Про каждую олимпиаду известно, сколько членов жюри должно участвовать в ее подготовке, а также время, требуемое на подготовку задач для нее. А именно, олимпиаду с номером i должны готовить pi человек в течение ti дней, причем подготовка олимпиады должна вестись непрерывный промежуток времени и закончиться ровно за день до олимпиады. Непосредственно в день олимпиады члены жюри, которые ее готовили, уже над ней не работают.
К примеру, если олимпиада состоится 9 декабря, и на ее подготовку требуется 7 человек и 6 дней, то все эти 7 членов жюри будут работать над задачами этой олимпиады с 3-го декабря по 8-е декабря (9-го декабря эти члены жюри уже не будут работать над задачами этой олимпиады, то есть некоторые из них могут начать готовить задачи какой-то другой олимпиады). А если олимпиада проводится 3 ноября и требует 5 дней подготовки, то члены жюри будут работать с 29-го октября по 2-е ноября.
Чтобы не перегружать членов жюри, было введено такое правило: один член жюри не может в один и тот же день работать над задачами для разных олимпиад. Напишите программу, которая определяет, какое наименьшее количество человек должно входить в состав жюри, чтобы все олимпиады могли быть подготовлены в срок.