"""Day 13."""
import re

with open("input") as f:
    data = f.read().rstrip().split("\n")

leave = int(data[0])
buses_orig = data[1].split(",")
buses = list(map(int, filter(lambda elem: elem != "x", buses_orig)))

lowest_time = None
lowest_id = None

for bus in buses:
    itr = 0
    while itr < leave:
        itr += bus
    diff = itr - leave
    if lowest_time is None:
        lowest_time = diff
        lowest_id = bus
    else:
        if diff < lowest_time:
            lowest_time = diff
            lowest_id = bus

res = lowest_time * lowest_id
print(res)
assert res == 1915


# Part 2

# My brute force, takes too long for big input

# step = max(buses)
# step_idx = buses_orig.index(str(step))
# print(step, step_idx)

# pos = step
# while True:
#     print(pos)
#     all_good = True
#     for idx, el in enumerate(buses_orig):
#         if el == 'x':
#             continue
#         temp = pos + idx - step_idx
#         if temp % int(el) != 0:
#             all_good = False
#             break
#     if all_good:
#         print(pos - step_idx)
#         break
#     pos += step


# Peter norvig's genius way


def wait(id, t):
    return 0 if t % id == 0 else id - t % id

time = 0
step = 1
schedule = {t: int(id) for t, id in enumerate(buses_orig) if id != 'x'}
for t in schedule:
    while wait(schedule[t], time + t):
        time += step
    step *= schedule[t]
print(time)

assert time == 294354277694107