CF254B.Jury Size

In 2013, the writers of Berland State University should prepare problems for n Olympiads. We will assume that the Olympiads are numbered with consecutive integers from 1 to n. For each Olympiad we know how many members of the jury must be involved in its preparation, as well as the time required to prepare the problems for her. Namely, the Olympiad number i should be prepared by p__i people for t__i days, the preparation for the Olympiad should be a continuous period of time and end exactly one day before the Olympiad. On the day of the Olympiad the juries who have prepared it, already do not work on it.

For example, if the Olympiad is held on December 9th and the preparation takes 7 people and 6 days, all seven members of the jury will work on the problems of the Olympiad from December, 3rd to December, 8th (the jury members won't be working on the problems of this Olympiad on December 9th, that is, some of them can start preparing problems for some other Olympiad). And if the Olympiad is held on November 3rd and requires 5 days of training, the members of the jury will work from October 29th to November 2nd.

In order not to overload the jury the following rule was introduced: one member of the jury can not work on the same day on the tasks for different Olympiads. Write a program that determines what the minimum number of people must be part of the jury so that all Olympiads could be prepared in time.

2013 年，Berland 国立大学的出题人需要为 n 场奥林匹克竞赛准备题目。我们假定这些奥林匹克竞赛按连续整数编号，从 1 到 n。对于每场奥林匹克竞赛，我们已知其题目准备所需的评委人数以及所需时间。具体而言，第 i 场奥林匹克竞赛需由 p__i 人花费 t__i 天完成准备；该准备工作必须是连续的一段时间，且必须恰好在奥林匹克竞赛举行前一日结束。在奥林匹克竞赛举行的当天，负责该竞赛准备工作的评委将不再继续为此竞赛工作。

例如，若某场奥林匹克竞赛于 12 月 9 日举行，且准备工作需 7 人、耗时 6 天，则这 7 名评委将从 12 月 3 日至 12 月 8 日（含）连续工作（评委们在 12 月 9 日不为此竞赛工作，因此其中部分人可开始为其他奥林匹克竞赛准备题目）。又如，若某场奥林匹克竞赛于 11 月 3 日举行，且准备需 5 天，则评委们的工作时间为 10 月 29 日至 11 月 2 日（含）。

为避免评委工作过载，特引入如下规则：一名评委不得在同一天为多场奥林匹克竞赛同时工作。请编写一个程序，计算为确保所有奥林匹克竞赛均能按时完成准备所需的评委最小总人数。

The first line contains integer n — the number of Olympiads in 2013 (1 ≤ n ≤ 100). Each of the following n lines contains four integers m__i, d__i, p__i and t__i — the month and day of the Olympiad (given without leading zeroes), the needed number of the jury members and the time needed to prepare the i-th Olympiad (1 ≤ m__i ≤ 12, d__i ≥ 1, 1 ≤ p__i, t__i ≤ 100), d__i doesn't exceed the number of days in month m__i. The Olympiads are given in the arbitrary order. Several Olympiads can take place in one day.

Use the modern (Gregorian) calendar in the solution. Note that all dates are given in the year 2013. This is not a leap year, so February has 28 days. Please note, the preparation of some Olympiad can start in 2012 year.

第一行包含一个整数 $n$ —— 2013 年举办的奥林匹克竞赛场次数（$1 \leq n \leq 100$）。接下来的 $n$ 行中，每行包含四个整数 $m_i$、$d_i$、$p_i$ 和 $t_i$ —— 分别表示第 $i$ 场奥林匹克竞赛的举办月份和日期（不带前导零）、所需裁判员人数以及为第 $i$ 场奥林匹克竞赛做准备所需的时间（$1 \leq m_i \leq 12$，$d_i \geq 1$，$1 \leq p_i, t_i \leq 100$），其中 $d_i$ 不超过该月 $m_i$ 的天数。各场奥林匹克竞赛的输入顺序是任意的。同一天内可以举办多场奥林匹克竞赛。

请在解答中使用现代公历（Gregorian calendar）。注意：所有日期均属于 2013 年。2013 年不是闰年，因此 2 月有 28 天。请注意，某些奥林匹克竞赛的准备工作可能始于 2012 年。

Print a single number — the minimum jury size.

输出一个整数——最小的陪审团人数。