ニート君は1年12ヶ月毎月30日まで計360日の世界線で暮らしています。その世界では毎年同じ日程のN個の連休が世界中の人に適用されていました。連休iはMi月Di日から始まる連続したVi日間です。
ニート君はNEETなので連休に関係なく毎日休みです。ある日ニート君は珍しく出かけようと思いましたが、人混みが嫌いなので、連休の影響で混雑する日はなるべく外に出たくありません。そこで、ニート君は以下の方法で各日の混雑度を計算し、混雑度が一番小さい日を探そうとしています。
1年の中で一番小さい混雑度を出力してください。 ただし、連休iは年を跨ぐ事があります。また、連休の日程は重複する事があります。
入力は以下の形式で与えられる。
N M1 D1 V1 S1 M2 D2 V2 S2 ... MN DN VN SN
1行目に整数Nが与えられる。
2行目からN+1行目に整数Mi, Di, Vi, Siが空白区切りで与えられる。(1 ≤ i ≤ N)
入力は以下の条件を満たす。
一番小さい混雑度を1行に出力する。
1 1 1 359 1
0
2 2 4 25 306 1 9 7 321
158
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
297