# Input: lines like
#          Button A: X+#, Y+#
#          Button B: X+#, Y+#
#          Prize: X=#, Y=#
#        separated by blank lines
# Output: if it costs 3 tokens to push A and 1 to push B,
#         what's the cheapest way to get from 0, 0 to prize location?
#         (max 100 pushes per button)
#         total cost across all sets of three lines

def get_cheapest_cost(ax, ay, bx, by, px, py):
  cheapest_cost = -1
  for na in range(101):
    nb = int((px - na * ax) / bx)
    if nb < 0 or nb > 100:
      continue
    if (na * ax) + (nb * bx) == px and (na * ay) + (nb * by) == py:
      cost = 3 * na + nb
      if cheapest_cost == -1 or cheapest_cost > cost:
        cheapest_cost = cost
  return cheapest_cost

button_a = []
button_b = []
prize = []

file = open("13_input.txt", "r")
line_count = 0
for line in file:
  line = line.replace("\n", "")
  line_count += 1
  if line_count % 4 == 1:
    line = line.replace("Button A: X+", "")
    line = line.replace(", Y+", " ")
    parts = line.split(" ")
    button_a.append([int(parts[0]), int(parts[1])])
    continue
  if line_count % 4 == 2:
    line = line.replace("Button B: X+", "")
    line = line.replace(", Y+", " ")
    parts = line.split(" ")
    button_b.append([int(parts[0]), int(parts[1])])
    continue
  if line_count % 4 == 3:
    line = line.replace("Prize: X=", "")
    line = line.replace(", Y=", " ")
    parts = line.split(" ")
    prize.append([int(parts[0]), int(parts[1])])
    continue

total = 0
for index in range(len(button_a)):
  cost = get_cheapest_cost(button_a[index][0], button_a[index][1], button_b[index][0], button_b[index][1], prize[index][0], prize[index][1])
  if cost >= 0:
    total += cost
print (total)