← 返回题目列表

Codeforces · 254/B

B. 陪审团规模

中文机器翻译题面 查看原题

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