import re


with open('input.txt') as fh:
	s = fh.read()
	l = s.strip().split('\n\n')
	assert len(l) == 3
	assert l[1].startswith('your ticket:\n')
	assert l[2].startswith('nearby tickets:\n')

	rules = {}
	for line in l[0].split('\n'):
		m = re.match('(.+): ([0-9]+)-([0-9]+) or ([0-9]+)-([0-9]+)', line)
		rules[m[1]] = [int(i) for i in m.groups()[1:]]

	line = l[1].split('\n')[1]
	my_ticket = [int(i) for i in line.split(',')]

	nearby_tickets = [
		[int(i) for i in line.split(',')]
		for line in l[2].split('\n')[1:]
	]


def find_possible_rules(x):
	return set([
		key
		for key, rule in rules.items()
		if (x >= rule[0] and x <= rule[1])
		or (x >= rule[2] and x <= rule[3])
	])


def part1():
	result = 0
	for ticket in nearby_tickets:
		for x in ticket:
			if not find_possible_rules(x):
				result += x
	print(result)


def part2():
	n = len(my_ticket)
	value = dict()
	total_possible = [set(rules.keys()) for _ in range(n)]

	for ticket in nearby_tickets:
		possible = [find_possible_rules(x) for x in ticket]
		if all(possible):
			for i in range(n):
				total_possible[i] &= possible[i]

	while True:
		# if a key is the only possible value for a position, it can be
		# removed from all other positions
		for i, p in enumerate(total_possible):
			if len(p) == 1:
				for key in p:
					for j in range(n):
						if i != j and key in total_possible[j]:
							total_possible[j].remove(key)
				break

		# if a key only appears in one position, all other keys can be
		# removed from that position
		for key in rules.keys():
			candidates = [p for p in total_possible if key in p]
			if len(candidates) == 1:
				candidates[0] &= {key}

		result = 1
		for key in rules.keys():
			if key.startswith('departure'):
				candidates = [i for i, p in enumerate(total_possible) if key in p]
				if len(candidates) != 1:
					break
				result *= my_ticket[candidates[0]]
		else:
			print(result)
			return

part1()
part2()