The year of 2012 is coming...

According to an ancient choradrican legend in this very year, in 2012, Diablo and his brothers Mephisto and Baal will escape from hell, and innumerable hordes of demons will enslave the human world. But seven brave heroes have already gathered on the top of a mountain Arreat to protect us mere mortals from the effect of this terrible evil.

The seven great heroes are: amazon Anka, barbarian Chapay, sorceress Cleo, druid Troll, necromancer Dracul, paladin Snowy and a professional hit girl Hexadecimal. Heroes already know how much experience will be given for each of the three megabosses: a for Mephisto, b for Diablo and c for Baal.

Here's the problem: heroes are as much as seven and megabosses are only three! Then our heroes decided to split into three teams, where each team will go to destroy their own megaboss. Each team member will receive a <image> of experience, rounded down, where x will be the amount of experience for the killed megaboss and y — the number of people in the team.

Heroes do not want to hurt each other's feelings, so they want to split into teams so that the difference between the hero who received the maximum number of experience and the hero who received the minimum number of experience were minimal. Since there can be several divisions into teams, then you need to find the one in which the total amount of liking in teams were maximum.

It is known that some heroes like others. But if hero p likes hero q, this does not mean that the hero q likes hero p. No hero likes himself.

The total amount of liking in teams is the amount of ordered pairs (p, q), such that heroes p and q are in the same group, and hero p likes hero q (but it is not important if hero q likes hero p). In case of heroes p and q likes each other and they are in the same group, this pair should be counted twice, as (p, q) and (q, p).

A team can consist even of a single hero, but it is important that every megaboss was destroyed. All heroes must be involved in the campaign against evil. None of the heroes can be in more than one team.

It is guaranteed that every hero is able to destroy any megaboss alone.

Input

The first line contains a single non-negative integer n (0 ≤ n ≤ 42) — amount of liking between the heroes. Next n lines describe liking in the form "p likes q", meaning that the hero p likes the hero q (p ≠  q). Every liking is described in the input exactly once, no hero likes himself.

In the last line are given three integers a, b and c (1 ≤ a, b, c ≤ 2·109), separated by spaces: the experience for Mephisto, the experience for Diablo and experience for Baal.

In all the pretests, except for examples from the statement, the following condition is satisfied: a = b = c.

Output

Print two integers — the minimal difference in the experience between two heroes who will receive the maximum and minimum number of experience points, and the maximal total amount of liking in teams (the number of friendships between heroes that end up in one team).

When calculating the second answer, the team division should satisfy the difference-minimizing contraint. I.e. primary you should minimize the difference in the experience and secondary you should maximize the total amount of liking.

Examples

Input

3
Troll likes Dracul
Dracul likes Anka
Snowy likes Hexadecimal
210 200 180


Output

30 3


Input

2
Anka likes Chapay
Chapay likes Anka
10000 50 50


Output

1950 2

Note

A note to first example: it the first team should be Dracul, Troll and Anka, in the second one Hexadecimal and Snowy, and in the third Cleo и Chapay.

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation

Complete search


Solutions:
from itertools import combinations, product
Teams = [[1, 1, 5], [1, 2, 4], [1, 3, 3], [2, 2, 3]]
Names = {}
Names['Anka'] = 0
Names['Chapay'] = 1
Names['Cleo'] = 2
Names['Dracul'] = 3
Names['Hexadecimal'] = 4
Names['Snowy'] = 5
Names['Troll'] = 6
graph = [[0] * 7 for _ in range(7)]
N = int(input())
for _ in range(N):
	(p, q) = input().split(' likes ')
	p = Names[p]
	q = Names[q]
	graph[p][q] = 1
(a, b, c) = sorted(map(int, input().split()))
E_diff_star = float('inf')
team_all = []
for (t1, t2, t3) in Teams:
	E = [a // t1, b // t2, c // t3]
	E_diff = max(E) - min(E)
	if E_diff < E_diff_star:
		E_diff_star = E_diff
		team_all = [[t1, t2, t3]]
	elif E_diff == E_diff_star:
		team_all.append([t1, t2, t3])
liking = 0
for team in team_all:
	for te2 in combinations(set(range(7)), team[2]):
		te2 = set(te2)
		left = set(range(7)) - te2
		L2 = sum((graph[p][q] for (p, q) in product(te2, te2)))
		for te1 in combinations(left, team[1]):
			te1 = set(te1)
			te0 = left - te1
			L1 = sum((graph[p][q] for (p, q) in product(te1, te1)))
			L0 = sum((graph[p][q] for (p, q) in product(te0, te0)))
			L = L2 + L1 + L0
			if L > liking:
				liking = L
print(E_diff_star, liking)


from itertools import combinations

def main():
	heroes = ('Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal')
	sympaty = [[False] * 7 for _ in range(7)]
	for _ in range(int(input())):
		(a, _, b) = input().split()
		sympaty[heroes.index(a)][heroes.index(b)] = True
	(a, b, c) = map(int, input().split())
	(tmp, res) = ([], [])
	for i in range(1, 6):
		for j in range(1, 7 - i):
			t = (int(a / i), int(b / j), int(c / (7 - i - j)))
			tmp.append((max(t) - min(t), i, j))
	delta = min(tmp)[0]
	for (i, j) in ((i, j) for (x, i, j) in tmp if x == delta):
		for aa in combinations(range(7), i):
			rest = [x for x in range(7) if x not in aa]
			for bb in combinations(rest, j):
				res.append(sum((sum((sympaty[x][y] for x in xy for y in xy)) for xy in (aa, bb, [x for x in rest if x not in bb]))))
	print(delta, max(res))
main()


import itertools
heroes = ['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']
n = int(input())
edges = []
for i in range(n):
	(p, likes, q) = input().split()
	edges.append((heroes.index(p), heroes.index(q)))
boss_xp = list(map(int, input().split()))
min_difference = float('inf')
max_liking = float('-inf')
for assignment in itertools.product(range(3), repeat=7):
	assignment_heroes = [[hero for (hero, boss) in enumerate(assignment) if boss == i] for i in range(3)]
	if any((len(attackers) == 0 for attackers in assignment_heroes)):
		continue
	xp_division = [xp // len(attackers) for (xp, attackers) in zip(boss_xp, assignment_heroes)]
	difference = max(xp_division) - min(xp_division)
	if difference < min_difference:
		min_difference = difference
		max_liking = sum((len([(p, q) for (p, q) in edges if p in attackers and q in attackers]) for attackers in assignment_heroes))
	elif difference == min_difference:
		liking = sum((len([(p, q) for (p, q) in edges if p in attackers and q in attackers]) for attackers in assignment_heroes))
		max_liking = max(max_liking, liking)
print('%d %d' % (min_difference, max_liking))


from itertools import *
p = {'An': 0, 'Ch': 1, 'Cl': 2, 'Tr': 3, 'Dr': 4, 'Sn': 5, 'He': 6}

def f():
	(u, l, v) = input().split()
	return (p[u[:2]], p[v[:2]])
s = [f() for k in range(int(input()))]
(a, b, c) = map(int, input().split())
d = l = 9000000000.0
for i in range(1, 6):
	for j in range(1, 7 - i):
		k = 7 - i - j
		t = [a // i, b // j, c // k]
		t = max(t) - min(t)
		if t < d:
			(d, l) = (t, 0)
		if t == d:
			for q in set(permutations([0] * i + [1] * j + [2] * k)):
				l = max(l, sum((q[u] == q[v] for (u, v) in s)))
print(d, l)


import math
import itertools
N = int(input())
likes = [input() for i in range(N)]
likes = [line.split() for line in likes]
likes = [(words[0], words[2]) for words in likes]
(a, b, c) = (float(val) for val in input().split())
min_diff = max(a, b, c)
possible_groups = []
for i in range(1, 7 - 1):
	for j in range(1, 7 - i):
		a_e = math.floor(a / i)
		b_e = math.floor(b / j)
		c_e = math.floor(c / (7 - i - j))
		diff = max(a_e, b_e, c_e) - min(a_e, b_e, c_e)
		if diff < min_diff:
			min_diff = diff
			possible_groups = [(i, j)]
		elif diff == min_diff:
			possible_groups.append((i, j))
max_likes = 0
for order in itertools.permutations(['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']):
	for (i, j) in possible_groups:
		likes_count = 0
		seta = set(order[:i])
		setb = set(order[i:i + j])
		setc = set(order[i + j:])
		for (p, q) in likes:
			if p in seta and q in seta:
				likes_count += 1
			if p in setb and q in setb:
				likes_count += 1
			if p in setc and q in setc:
				likes_count += 1
		max_likes = max(max_likes, likes_count)
print(f'{min_diff} {max_likes}')


import itertools

def sets(heros, min_elem, max_elem):
	ans = []
	if max_elem > len(heros):
		max_elem = len(heros)
	if min_elem > len(heros):
		return []
	for i in range(min_elem, max_elem + 1):
		s = itertools.combinations(heros, i)
		for ss in s:
			ans.append(ss)
	return ans

def update(set1, set2, set3, x, y, a, b, c, pairs):
	q = a // len(set1)
	w = b // len(set2)
	e = c // len(set3)
	m = max(abs(q - w), abs(w - e), abs(e - q))
	if m == x:
		x = m
		y1 = 0
		for p in pairs:
			if p[0] in set1 and p[1] in set1 or (p[0] in set2 and p[1] in set2) or (p[0] in set3 and p[1] in set3):
				y1 += 1
		if y < y1:
			y = y1
	if m < x:
		x = m
		y = 0
		for p in pairs:
			if p[0] in set1 and p[1] in set1 or (p[0] in set2 and p[1] in set2) or (p[0] in set3 and p[1] in set3):
				y += 1
	return (x, y)

def solve(n, pairs, a, b, c):
	(x, y) = (100000000000000, 0)
	heros = ['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']
	for_set1 = sets(heros, 1, 5)
	for set1 in for_set1:
		heros2 = []
		for i in heros:
			if i not in set1:
				heros2.append(i)
		for_set2 = sets(heros2, 1, 7 - len(set1))
		for set2 in for_set2:
			set3 = []
			for i in heros2:
				if i not in set2:
					set3.append(i)
			if len(set1) > 0 and len(set2) > 0 and (len(set3) > 0):
				(x, y) = update(set1, set2, set3, x, y, a, b, c, pairs)
	return (x, y)
n = int(input())
pairs = []
for i in range(n):
	(x, _, y) = input().split()
	pairs.append((x, y))
(a, b, c) = input().split()
a = int(a)
b = int(b)
c = int(c)
(x, y) = solve(a, pairs, a, b, c)
print(x, y)


minn = [10 ** 10]
maxx = [0]
A = []
B = []
C = []
N = ['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']
k = {}
T = [0] * 7
for i in range(7):
	k[N[i]] = i
C = []
for i in range(7):
	C.append([0] * 7)

def Solve(i):
	if i == 7:
		a = []
		b = []
		c = []
		for j in range(7):
			if T[j] == 1:
				a.append(j)
			elif T[j] == 2:
				b.append(j)
			else:
				c.append(j)
		L = 0
		if len(a) == 0 or len(b) == 0 or len(c) == 0:
			return
		for item in a:
			for q in a:
				if C[item][q]:
					L += 1
		for item in b:
			for q in b:
				if C[item][q]:
					L += 1
		for item in c:
			for q in c:
				if C[item][q]:
					L += 1
		for x in range(3):
			for y in range(3):
				if x == y:
					continue
				for z in range(3):
					if x == z or y == z:
						continue
					e = min((X[x] // len(a), X[y] // len(b), X[z] // len(c)))
					ee = max((X[x] // len(a), X[y] // len(b), X[z] // len(c)))
					if ee - e < minn[0]:
						minn[0] = ee - e
						maxx[0] = L
					elif ee - e == minn[0]:
						if maxx[0] < L:
							maxx[0] = L
		return
	T[i] = 1
	Solve(i + 1)
	T[i] = 2
	Solve(i + 1)
	T[i] = 3
	Solve(i + 1)
	return
n = int(input())
for i in range(n):
	s = input().split()
	C[k[s[0]]][k[s[2]]] = 1
X = list(map(int, input().split()))
Solve(0)
print(minn[0], maxx[0])


heroes = ['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']
num_heroes = len(heroes)
likes = [[False for j in range(num_heroes)] for i in range(num_heroes)]
n = int(input())
for i in range(n):
	(u, _, v) = input().split()
	likes[heroes.index(u)][heroes.index(v)] = True
monster_points = list(map(int, input().split()))
num_monsters = len(monster_points)
assigned = num_heroes * [0]
assigned[num_heroes - 1] = -1

def next_assigned():
	pos = len(assigned) - 1
	while pos != -1 and assigned[pos] == num_monsters - 1:
		assigned[pos] = 0
		pos -= 1
	if pos == -1:
		return False
	assigned[pos] += 1
	return True
min_difference = 10 ** 10
max_liking = -1
while next_assigned():
	teams = [[] for i in range(num_monsters)]
	for (i, x) in enumerate(assigned):
		teams[x].append(i)
	if [] in teams:
		continue
	min_bonus = max_bonus = monster_points[0] // len(teams[0])
	for i in range(1, num_monsters):
		min_bonus = min(min_bonus, monster_points[i] // len(teams[i]))
		max_bonus = max(max_bonus, monster_points[i] // len(teams[i]))
	difference = max_bonus - min_bonus
	if difference > min_difference:
		continue
	liking = 0
	for team in teams:
		for u in team:
			for v in team:
				if likes[u][v]:
					liking += 1
	if difference == min_difference:
		max_liking = max(max_liking, liking)
		continue
	min_difference = difference
	max_liking = liking
print(min_difference, max_liking)


R = range
S = str.split
I = input
L = S('Anka Chapay Cleo Troll Dracul Snowy Hexadecimal')
h = {}
for i in R(7):
	h[L[i]] = i
d = [[] for i in R(9)]
for z in '0' * int(I()):
	(a, _, b) = S(I())
	d[h[a]] += [h[b]]
(a, b, c) = map(int, S(I()))
o = [10 ** 9, 0]

def C(q, w, e, n):
	if n == 7:
		if not (q and w and e):
			return
		p = [a // len(q), b // len(w), c // len(e)]
		p = max(p) - min(p)
		l = sum((k in g for g in (q, w, e) for h in g for k in d[h]))
		global o
		if o[0] > p or (o[0] == p and o[1] < l):
			o = (p, l)
	else:
		C(q + [n], w, e, n + 1)
		C(q, w + [n], e, n + 1)
		C(q, w, e + [n], n + 1)
C([], [], [], 0)
print(o[0], o[1])


from itertools import product, permutations, combinations
n = int(input())
names = {}
nex = 0
mama = 128
liking = [0] * mama
likes = [[0] * 7 for _ in range(7)]

def getName(name):
	global nex
	if name in names:
		return names[name]
	names[name] = nex
	nex += 1
	return names[name]
for _ in range(n):
	(a, b, c) = input().split()
	likes[getName(a)][getName(c)] = 1
bosses = [int(x) for x in input().split()]
part = [(0, 0, 0)]
dipart = 10 ** 10
for i in range(1, 4):
	for j in range(i, 7):
		k = 7 - i - j
		if k < j:
			continue
		for per in permutations(bosses):
			aa = (per[0] // i, per[1] // j, per[2] // k)
			difi = max(aa) - min(aa)
			if difi < dipart:
				dipart = difi
				part = [(i, j, k)]
			elif difi == dipart:
				part.append((i, j, k))
for (i, j) in product(range(7), repeat=2):
	if likes[i][j] == 0:
		continue
	mask = 1 << i | 1 << j
	for k in range(mama):
		if k & mask == mask:
			liking[k] += 1
nums = list(range(7))

def tonum(ite):
	r = 0
	for nu in ite:
		r |= 1 << nu
	return r
bea = 0
for (a, b, c) in part:
	for pera in combinations(range(7), a):
		lefta = [x for x in nums if x not in pera]
		for perb in combinations(lefta, b):
			perc = [x for x in lefta if x not in perb]
			susu = liking[tonum(pera)] + liking[tonum(perb)] + liking[tonum(perc)]
			if susu > bea:
				bea = susu
print(dipart, bea)


from itertools import product
n = int(input())
names_to_index = {'Anka': 0, 'Chapay': 1, 'Cleo': 2, 'Troll': 3, 'Dracul': 4, 'Snowy': 5, 'Hexadecimal': 6}
liking = set()
for i in range(n):
	(a, b, c) = input().split()
	liking.add((names_to_index[a], names_to_index[c]))
(diablo, baal, mefisto) = map(int, input().split())
results = set()

def sum_liking(heroes):
	s = 0
	for a in heroes:
		for b in heroes:
			if (a, b) in liking:
				s += 1
	return s
for a in product(*[range(1, 4)] * 7):
	if 1 in a and 2 in a and (3 in a):
		tmp_liking = sum_liking([i for i in range(7) if a[i] == 1]) + sum_liking([i for i in range(7) if a[i] == 2]) + sum_liking([i for i in range(7) if a[i] == 3])
		tmp = [diablo // a.count(1), baal // a.count(2), mefisto // a.count(3)]
		results.add((max(tmp) - min(tmp), tmp_liking))
		tmp = [diablo // a.count(1), baal // a.count(3), mefisto // a.count(2)]
		results.add((max(tmp) - min(tmp), tmp_liking))
		tmp = [diablo // a.count(2), baal // a.count(1), mefisto // a.count(3)]
		results.add((max(tmp) - min(tmp), tmp_liking))
		tmp = [diablo // a.count(3), baal // a.count(1), mefisto // a.count(2)]
		results.add((max(tmp) - min(tmp), tmp_liking))
		tmp = [diablo // a.count(2), baal // a.count(3), mefisto // a.count(1)]
		results.add((max(tmp) - min(tmp), tmp_liking))
		tmp = [diablo // a.count(3), baal // a.count(2), mefisto // a.count(1)]
		results.add((max(tmp) - min(tmp), tmp_liking))
final_result = (2 * 10 ** 9 + 10, 0)
for i in results:
	if final_result[0] > i[0]:
		final_result = i
	elif final_result[0] == i[0] and final_result[1] < i[1]:
		final_result = i
print(str(final_result[0]) + ' ' + str(final_result[1]))


names = ['Anka', 'Chapay', 'Cleo', 'Troll', 'Dracul', 'Snowy', 'Hexadecimal']
minDif = (10 ** 1000, 1)
totLikes = 0

def less(a, b):
	return a[0] * b[1] < a[1] * b[0]

def eq(a, b):
	return a[0] * b[1] == a[1] * b[0]

def rec(cur, groups):
	if cur == 7:
		global likes, exp, minDif, totLikes
		if 1 not in groups or 2 not in groups or 3 not in groups:
			return
		mx = (0, 1)
		mn = (10 ** 100, 1)
		curLike = 0
		for i in range(1, 4):
			curGroup = [x[0] for x in enumerate(groups) if x[1] == i]
			high = exp[i - 1] // len(curGroup)
			low = 1
			q = (high, low)
			if less(mx, q):
				mx = q
			if less(q, mn):
				mn = q
			for v in curGroup:
				for u in curGroup:
					curLike += likes[v][u]
		q = (mx[0] * mn[1] - mn[0] * mx[1], mn[1] * mx[1])
		if less(q, minDif):
			minDif = q
			totLikes = curLike
		elif eq(q, minDif):
			if curLike > totLikes:
				totLikes = curLike
	else:
		rec(cur + 1, groups + [1])
		rec(cur + 1, groups + [2])
		rec(cur + 1, groups + [3])
n = int(input())
likes = [[0 for i in range(len(names))] for j in range(len(names))]
for i in range(n):
	like = input().split(' ')
	likes[names.index(like[0])][names.index(like[2])] = 1
exp = list(map(int, input().split()))
rec(0, [])
print(minDif[0] // minDif[1], totLikes)


import itertools
n = int(input())
(a, b) = ([], {'An': 0, 'Ch': 1, 'Cl': 2, 'Tr': 3, 'Dr': 4, 'Sn': 5, 'He': 6})
for i in range(n):
	(x, y, z) = input().split()
	a.append([b[x[:2]], b[z[:2]]])
(m1, m2, m3) = map(int, input().split())
ans = 10 ** 9
mk = 10 ** 9
for k1 in range(1, 6):
	for k2 in range(1, 7 - k1):
		k3 = 7 - k1 - k2
		if k3 <= 0:
			continue
		c = [m1 // k1, m2 // k2, m3 // k3]
		d = max(c) - min(c)
		if d < ans:
			(ans, mk) = (d, 0)
		if d == ans:
			for e in set(itertools.permutations([0] * k1 + [1] * k2 + [2] * k3)):
				L = 0
				for f in a:
					if e[f[0]] == e[f[1]]:
						L += 1
				if mk < L:
					mk = L
print(ans, mk)


import sys
from array import array
from itertools import product

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
d = {'Anka': 0, 'Chapay': 1, 'Cleo': 2, 'Troll': 3, 'Dracul': 4, 'Snowy': 5, 'Hexadecimal': 6}
matrix = [[0] * 7 for _ in range(7)]
n = int(input())
for a in (input().split() for _ in range(n)):
	matrix[d[a[0]]][d[a[2]]] = 1
exp = tuple(map(int, input().split()))
delta = 10 ** 9
likes = 0
for num in product(range(1, 6), repeat=3):
	if sum(num) != 7:
		continue
	e = [exp[i] // num[i] for i in range(3)]
	if max(e) - min(e) > delta:
		continue
	flag = max(e) - min(e) == delta
	delta = max(e) - min(e)
	l = 0
	for p in product(range(3), repeat=7):
		if not all((p.count(i) == num[i] for i in range(3))):
			continue
		_l = 0
		for i in range(7):
			for j in range(7):
				if p[i] == p[j] and matrix[i][j]:
					_l += 1
		l = max(l, _l)
	if flag:
		likes = max(likes, l)
	else:
		likes = l
print(delta, likes)