2013年,伯兰州立大学的作家们应该为n届奥林匹克竞赛准备问题。我们假设奥运会用从 1 到 n 的连续整数进行编号。对于每届奥运会,我们都知道有多少评委会成员必须参与其准备工作,以及为她准备问题所需的时间。即,第i个奥数应由pi人准备ti天,奥数的准备工作应是连续的一段时间,并在奥数前一天结束。在奥林匹克竞赛当天,准备好的评审团已经不再进行工作。
例如,如果奥赛在12月9日举行,准备工作需要7个人6天,则所有7名评委会成员将从12月3日到12月8日处理奥数题(12月9日评委会成员不会处理本次奥数题,即其中一些人可以开始为其他一些奥数题做准备)。而如果奥赛在11月3日举行,需要5天的培训,那么评委会成员的工作时间为10月29日至11月2日。
为了不让评审团负担过重,引入了以下规则:一名评审团成员不能在同一天完成不同奥运会的任务。编写一个程序来确定评审团的最低人数,以便所有奥林匹克运动会都能及时做好准备。
输入
第一行包含整数 n — 2013 年奥运会的数量 (1 ≤ n ≤ 100)。接下来的 n 行每行包含四个整数 mi、di、pi 和 ti——奥运会的月份和日期(不带前导零)、所需的评审团成员人数以及准备第 i 届奥运会所需的时间(1 ≤ mi ≤ 12,di ≥ 1,1 ≤ pi,ti ≤ 100),di 不超过 mi 月份的天数。奥林匹克竞赛以任意顺序给出。一天之内可以举行几场奥运会。
在解决方案中使用现代(公历)日历。请注意,所有日期均以 2013 年为单位。这不是闰年,因此 2 月有 28 天。请注意,一些奥林匹克竞赛的筹备工作可能会在 2012 年开始。
输出
打印一个数字——陪审团的最小人数。
示例
输入 #1
2 5 23 1 2 3 13 2 3
输出 #1
2
输入 #2
3 12 9 2 1 12 8 1 3 12 8 2 2
输出 #2
3
输入 #3
1 1 10 1 13
输出 #3
1