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.


-----Input-----

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.


-----Output-----

Print a single number — the minimum jury size.


-----Examples-----
Input
2
5 23 1 2
3 13 2 3

Output
2

Input
3
12 9 2 1
12 8 1 3
12 8 2 2

Output
3

Input
1
1 10 1 13

Output
1

Difficulty: MEDIUM
Tags: Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
(w, r) = (open('output.txt', 'w'), open('input.txt', 'r'))
(s, y) = ([0] * 466, [0, 100, 131, 159, 190, 220, 251, 281, 312, 343, 373, 404, 434])
for i in range(int(r.readline())):
	(m, d, p, t) = map(int, r.readline().split())
	x = y[m] + d
	s[x] -= p
	s[x - t] += p
for i in range(465):
	s[i + 1] += s[i]
w.write(str(max(s)))


import sys
import datetime

def solve():
	n = int(input())
	count = [0] * 10000
	for i in range(n):
		(m, d, p, t) = map(int, input().split())
		end = datetime.date(2013, m, d).toordinal() - 734000
		for j in range(end - t, end):
			count[j] += p
	print(max(count))
if sys.hexversion == 50594544:
	sys.stdin = open('test.txt')
else:
	sys.stdin = open('input.txt')
	sys.stdout = open('output.txt', 'w')
solve()


fin = open('input.txt', 'r')
fout = open('output.txt', 'w')
day = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
table = []
for i in range(int(fin.readline())):
	table.append([int(i) for i in fin.readline().split()])
ans = [0] * 500
for it in table:
	days = sum(day[0:it[0]]) + it[1] + 100
	for i in range(1, it[3] + 1):
		ans[days - i] += it[2]
print(max(ans), file=fout)


from collections import Counter
dm = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

def dec(d):
	d[2] -= 1
	if d[2] == 0:
		d[1] -= 1
		if d[1] == 0:
			d[0] -= 1
			d[1] = 12
		d[2] = dm[d[1]]
f = open('input.txt', 'r')
c = Counter()
for i in range(int(f.readline())):
	d = [2013] + list(map(int, f.readline().split()))
	for j in range(d[4]):
		dec(d)
		c[10000 * d[0] + 100 * d[1] + d[2]] += d[3]
print(c.most_common()[0][1], file=open('output.txt', 'w'))


from sys import *
from bisect import *
from collections import *
from itertools import *
from fractions import *
from datetime import *
Input = []
stdin = open('input.txt', 'r')
stdout = open('output.txt', 'w')

def Out(x):
	stdout.write(str(x) + '\n')

def In():
	return stdin.readline().strip()

def inputGrab():
	for line in stdin:
		Input.extend(map(str, line.strip().split()))

def main():
	n = int(In())
	y = 2013
	Lst = []
	Max = -1
	for _ in range(n):
		Lst.append(list(map(int, In().split())))
		Max = max(Max, Lst[_][2])
	Lst.sort()
	Ans = Max
	for i in range(len(Lst) - 1):
		Tmp = Lst[i][2]
		for j in range(i + 1, len(Lst)):
			x = date(2013, Lst[i][0], Lst[i][1])
			y = date(2013, Lst[j][0], Lst[j][1])
			if x > y - timedelta(days=Lst[j][3]):
				Tmp += Lst[j][2]
		Ans = max(Ans, Tmp)
	Out(Ans)

def __starting_point():
	main()
__starting_point()


import sys

def getMaxJuries(juries, m, d, t, months):
	year = 1
	res = 0
	while t > 0:
		if d < 0:
			m -= 1
			if m < 0:
				m += 12
				year = 0
			d = months[m] - 1
		res = max(res, juries[year][m][d])
		d -= 1
		t -= 1
	return res

def setJury(juries, m, d, t, months, p):
	year = 1
	while t > 0:
		if d < 0:
			m -= 1
			if m < 0:
				m += 12
				year = 0
			d = months[m] - 1
		juries[year][m][d] += p
		d -= 1
		t -= 1

def __starting_point():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	months = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
	n = int(input())
	juriesNumber = 0
	juries = [[[0 for i in range(31)] for j in range(12)] for _ in range(2)]
	for i in range(n):
		(m, d, p, t) = [int(x) for x in input().split()]
		m -= 1
		d -= 2
		maxJuries = getMaxJuries(juries, m, d, t, months)
		if maxJuries + p > juriesNumber:
			juriesNumber += maxJuries + p - juriesNumber
		setJury(juries, m, d, t, months, p)
	print(juriesNumber)
__starting_point()


fin = open('input.txt', 'r')
fout = open('output.txt', 'w')
mon = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
ans = [0] * 500
ba = []
for i in range(int(fin.readline())):
	(m, d, p, t) = map(int, fin.readline().split())
	ba.append([m, d, p, t])
for i in ba:
	days = sum(mon[:i[0]]) + i[1] + 100
	for j in range(1, i[3] + 1):
		ans[days - j] += i[2]
print(max(ans), file=fout)


w = open('output.txt', 'w')
r = open('input.txt', 'r')
arr = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

def get_date(m, d):
	res = 0
	for i in range(m - 1):
		res += arr[i]
	return res + d
n = int(r.readline())
used = [0] * 366
for i in range(n):
	(m, d, p, t) = list(map(int, r.readline().split()))
	date = get_date(m, d)
	for i in range(max(0, date - t), date):
		used[i] += p
w.write(str(max(used)))


from sys import stdin, stdout

def get_time(m, d, t):
	month = ['dum', 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
	day = 0
	for i in range(1, m):
		day += month[i]
	day += d
	end = day
	start = end - t
	return (start, end)
stdin = open('input.txt', 'r')
stdout = open('output.txt', 'w')
n = int(stdin.readline().strip())
time_line = []
for _ in range(n):
	(m, d, p, t) = list(map(int, stdin.readline().split()))
	(start, end) = get_time(m, d, t)
	time_line.append([start, p])
	time_line.append([end, -p])
time_line = sorted(time_line, key=lambda x: (x[0], x[1]))
ans = 0
temp = 0
for i in range(len(time_line)):
	temp += time_line[i][1]
	ans = max(ans, temp)
stdout.write(str(ans))


def main():
	days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
	month2day = {}
	cnt = 0
	for i in range(9, 12 + 1):
		for j in range(1, days_in_month[i - 1] + 1):
			month2day[i, j, 12] = cnt
			cnt += 1
	for i in range(1, 12 + 1):
		for j in range(1, days_in_month[i - 1] + 1):
			month2day[i, j, 13] = cnt
			cnt += 1
	with open('input.txt') as f:
		test = f.readlines()
	n = int(test[0].strip())
	days = [0] * len(month2day)
	for i in range(1, n + 1):
		(m, d, p, t) = map(int, test[i].strip().split())
		R = month2day[m, d, 13] - 1
		L = R - t + 1
		days[L] += p
		days[R + 1] -= p
	acc = [days[0]]
	for i in range(1, len(days)):
		acc.append(acc[-1] + days[i])
	with open('output.txt', 'w') as f:
		f.write(str(max(acc)))

def __starting_point():
	main()
__starting_point()


from datetime import date, timedelta
import math
w = open('output.txt', 'w')
r = open('input.txt', 'r')
oplympiads = []
min_date = date(2014, 1, 1)
max_date = date(2011, 1, 1)
n = int(r.readline())
for _ in range(n):
	(m, d, p, t) = map(int, r.readline().split())
	oplympiads.append((m, d, p, t))
	if date(2013, m, d) > max_date:
		max_date = date(2013, m, d)
	if date(2013, m, d) - timedelta(t) < min_date:
		min_date = date(2013, m, d) - timedelta(t)
days_needed = (max_date - min_date).days
number_of_workers_in_day = [0] * days_needed
for (m, d, p, t) in oplympiads:
	for dte in range(t):
		number_of_workers_in_day[(date(2013, m, d) - timedelta(t - dte) - min_date).days] += p
w.write('{}'.format(max(number_of_workers_in_day)))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
sys.setrecursionlimit(pow(10, 6))
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return list(map(int, data().split()))

def ssp():
	return list(map(str, data().split()))

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def jury_size(a):
	date = start[a]
	dp[' '.join(map(str, end[a]))] += jury[a]
	while date != end[a]:
		dp[' '.join(map(str, date))] += jury[a]
		if date[0] in tone and date[1] == 31:
			date[0] += 1
			date[1] = 1
		elif date[0] == 2 and date[1] == 28:
			date[0] += 1
			date[1] = 1
		elif date[0] not in tone and date[1] == 30:
			date[0] += 1
			date[1] = 1
		else:
			date[1] += 1
(start, end, jury) = ([], [], [])
dp = dd(int)
tone = [1, 3, 5, 7, 8, 10, 12, 0, -2]
n = int(data())
for i in range(n):
	(m, d, p, t) = sp()
	if d > 1:
		end.append([m, d - 1])
	else:
		temp = d
		if m - 1 in tone:
			temp = 31
		elif m == 3:
			temp = 28
		else:
			temp = 30
		end.append([m - 1, temp])
	temp = d
	while t >= temp:
		m -= 1
		if m in tone:
			temp += 31
		elif m == 2:
			temp += 28
		else:
			temp += 30
	ed = temp - t
	start.append([m, ed])
	jury.append(p)
for i in range(n):
	jury_size(i)
out(max(dp.values()))


import sys
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
di = {}
k = 1
days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
for i in range(12):
	for j in range(days[i]):
		di[i + 1, j + 1] = k
		k += 1
n = int(input())
a = [0] * 512
for _ in range(n):
	(m, d, p, t) = map(int, input().split())
	temp = di[m, d]
	for x in range(temp - t, temp):
		a[x] += p
print(max(a))