Problem B: Hating Crowd

Problem

ニート君は1年12ヶ月毎月30日まで計360日の世界線で暮らしています。その世界では毎年同じ日程のN個の連休が世界中の人に適用されていました。連休iはM_i月D_i日から始まる連続したV_i日間です。

ニート君はNEETなので連休に関係なく毎日休みです。ある日ニート君は珍しく出かけようと思いましたが、人混みが嫌いなので、連休の影響で混雑する日はなるべく外に出たくありません。そこで、ニート君は以下の方法で各日の混雑度を計算し、混雑度が一番小さい日を探そうとしています。

• ある日付xが、連休iによって受ける影響の度合を表す数値は、日付xが連休iの中に含まれていればS_iであり、そうでなければ、 max( 0, S_i − min ( xから連休iの初日までの日数 , 連休iの最終日からxまでの日数 ) )である
• ある日付xの混雑度は、N個の連休から受ける影響の度合の中で、最も大きく受ける影響の度合となる

1年の中で一番小さい混雑度を出力してください。 ただし、連休iは年を跨ぐ事があります。また、連休の日程は重複する事があります。

Input

入力は以下の形式で与えられる。

N
M1 D1 V1 S1
M2 D2 V2 S2
...
MN DN VN SN

1行目に整数Nが与えられる。
2行目からN+1行目に整数M_i, D_i, V_i, S_iが空白区切りで与えられる。（1 ≤ i ≤ N）

Constraints

入力は以下の条件を満たす。

• 1 ≤ N ≤ 100
• 1 ≤ M_i ≤ 12
• 1 ≤ D_i ≤ 30
• 1 ≤ V_i, S_i ≤ 360

Output

一番小さい混雑度を1行に出力する。

Sample Input 1

1
1 1 359 1

Sample Output 1

0

Sample Input 2

2
2 4 25 306
1 9 7 321

Sample Output 2

158

Sample Input 3

8
2 9 297 297
8 6 359 211
8 16 28 288
7 9 113 143
3 18 315 190
10 18 277 300
9 5 276 88
3 5 322 40

Sample Output 3

297

Note

Link

 

---