B. Размер жюри
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
input.txt
вывод
output.txt

В 2013-м году авторский коллектив Берляндского государственного университета должен подготовить задачи к n олимпиадам. Будем считать, что олимпиады пронумерованы последовательными целыми числами от 1 до n. Про каждую олимпиаду известно, сколько членов жюри должно участвовать в ее подготовке, а также время, требуемое на подготовку задач для нее. А именно, олимпиаду с номером i должны готовить pi человек в течение ti дней, причем подготовка олимпиады должна вестись непрерывный промежуток времени и закончиться ровно за день до олимпиады. Непосредственно в день олимпиады члены жюри, которые ее готовили, уже над ней не работают.

К примеру, если олимпиада состоится 9 декабря, и на ее подготовку требуется 7 человек и 6 дней, то все эти 7 членов жюри будут работать над задачами этой олимпиады с 3-го декабря по 8-е декабря (9-го декабря эти члены жюри уже не будут работать над задачами этой олимпиады, то есть некоторые из них могут начать готовить задачи какой-то другой олимпиады). А если олимпиада проводится 3 ноября и требует 5 дней подготовки, то члены жюри будут работать с 29-го октября по 2-е ноября.

Чтобы не перегружать членов жюри, было введено такое правило: один член жюри не может в один и тот же день работать над задачами для разных олимпиад. Напишите программу, которая определяет, какое наименьшее количество человек должно входить в состав жюри, чтобы все олимпиады могли быть подготовлены в срок.

Входные данные

В первой строке записано целое число n — количество олимпиад в 2013-м году (1 ≤ n ≤ 100). Каждая из следующих n строк содержит по четыре целых числа mi, di, pi и ti — месяц и день олимпиады (заданы без лидирующих нулей), требуемое количество членов жюри и время, требуемое на подготовку i-й олимпиады (1 ≤ mi ≤ 12, di ≥ 1, 1 ≤ pi, ti ≤ 100), di не превосходит количества дней в месяце mi. Олимпиады заданы в произвольном порядке. В один день может проводиться несколько олимпиад.

Для решения задачи используйте современный (Григорианский) календарь. Обратите внимание, все даты заданы в 2013 году. Этот год не является високосным, следовательно, в феврале 28 дней. Обратите внимание, подготовка некоторой олимпиады может начаться в 2012 году.

Выходные данные

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

Примеры
Входные данные
2
5 23 1 2
3 13 2 3
Выходные данные
2
Входные данные
3
12 9 2 1
12 8 1 3
12 8 2 2
Выходные данные
3
Входные данные
1
1 10 1 13
Выходные данные
1