Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[None] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = defaultdict(set)
    dp[(0, 0)].add(X[0][0])
    dp[(0, 0)].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()
            if h > 0:
                for d in dp[(h - 1, w)]:
                    s.add(d + x)
                    s.add(d - x)

            if w > 0:
                for d in dp[(h, w - 1)]:
                    s.add(d + x)
                    s.add(d - x)

            dp[(h, w)] = s

    ans = min([abs(s) for s in dp[(H - 1, W - 1)]])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

H, W, M = [int(i) for i in input().split()]

cnt_dict_h = {}
cnt_dict_w = {}
bomb_list = []

for i in range(M):
    h, w = [int(i)-1 for i in input().split()]
    bomb_list.append((h,w))
    cnt_dict_h.setdefault(h, 0)
    cnt_dict_h[h] += 1
    cnt_dict_w.setdefault(w, 0)
    cnt_dict_w[w] += 1

max_h_key_list = [kv[0] for kv in cnt_dict_h.items() if kv[1] == max(cnt_dict_h.values())]
max_w_key_list = [kv[0] for kv in cnt_dict_w.items() if kv[1] == max(cnt_dict_w.values())]
max_h = max(cnt_dict_h.values())
max_w = max(cnt_dict_w.values())

bomb_num = max_h + max_w - 1

flag = False

for h in max_h_key_list:
    for w in max_w_key_list:
        if (h, w) not in bomb_list:
            bomb_num = max_h + max_w
            break
        else :
            continue
        break
        
print(bomb_num)

### FIXED CODE ###

H, W, M = [int(i) for i in input().split()]

sum_h = [0] * W
sum_w = [0] * H
bomb_list = set()

for _ in range(M):
    h, w = [int(i) for i in input().split()]
    h -= 1
    w -= 1
    bomb_list.add((h,w))
    sum_h[w] += 1
    sum_w[h] += 1

max_sum_h = max(sum_h)
max_sum_w = max(sum_w)
output = max_sum_h + max_sum_w - 1

max_bombs_h = [h for h in range(H) if sum_w[h] == max_sum_w]
max_bombs_w = [w for w in range(W) if sum_h[w] == max_sum_h]

for h in max_bombs_h:
    for w in max_bombs_w:
        if (h, w) not in bomb_list:
            output = max_sum_h + max_sum_w
            break
        else:
            continue
        break
        
print(output)
### BUGGY CODE ###

N,M=map(int,input().split())
li=[]
H=list(map(int,input().split()))

for i in range(M):
    A,B=map(int,input().split())
    if H[A-1]>H[B-1]:
        if B in li:
            pass
        else:
            li.append(B)
    elif H[A-1]<H[B-1]:
        if A in li:
            pass
        else:
            li.append(A)
    else:
        if A in li and B in li:
            pass
        elif A in li:
            li.append(B)
        elif B in li:
            li.append(A)
        else:
            li.append(A)
            li.append(B)

print(N-len(li))


### FIXED CODE ###

N,M=map(int,input().split())
h=list(map(int,input().split()))
li=[1]*N
for i in range(M):
    a,b=list(map(int,input().split()))
    if h[a-1]>h[b-1]:
        li[b-1]*=0
    elif h[a-1]==h[b-1]:
        li[a-1]*=0
        li[b-1]*=0
    else:
        li[a-1]*=0

ans=li.count(1)
print(ans)
### BUGGY CODE ###

def main():
    from sys import stdin

    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = stdin.readline()
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append([h, w])
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append([nh, nw])
                    cnt += 1
        q = nextq
    print(ans)
main()


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    g = []
    q = []
    cnt = 0
    for h in range(H):
        A = str(input())
        row = []
        for w in range(W):
            row.append(A[w])
            if A[w] == '#':
                cnt += 1
                q.append([h, w])
        g.append(row)
    ans = 0
    dh = [1, 0, 0, -1]
    dw = [0, -1, 1, 0]
    while cnt < H * W:
        ans += 1
        nextq = []
        while q:
            h, w = q.pop()
            for i in range(4):
                nh = h + dh[i]
                nw = w + dw[i]
                if 0 <= nh < H and 0 <= nw < W and g[nh][nw] == '.':
                    g[nh][nw] = '#'
                    nextq.append([nh, nw])
                    cnt += 1
        q = nextq
    print(ans)
main()
### BUGGY CODE ###

from collections import deque

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

q = deque()
for i in a:
    q.append([i])

ans = 0
while q:
    now = q.popleft()
    n = len(now)
    if n == 3:
        ans += 1
    elif n == 2:
        for x in c:
            if now[-1] < x:
                q.append(now + [x])
    elif n == 1:
        for y in b:
            if now[-1] < y:
                q.append(now + [y])

print(ans)


### FIXED CODE ###

import bisect

n = int(input())
a = sorted(list(map(int, input().split())))
b = list(map(int, input().split()))
c = sorted(list(map(int, input().split())))

ans = 0
for i in b:
    a_pos = bisect.bisect_left(a, i)
    c_pos = n - bisect.bisect_right(c, i)
    ans += a_pos * c_pos

print(ans)
### BUGGY CODE ###

import math
import sys

n, m = map(int, input().split())
a_list = [-1]
for _ in range(m):
    a_list.append(int(input()))
a_list.append(n + 1)

patterns = []
for i in range(1, len(a_list)):
    sub = a_list[i] - a_list[i-1] - 1
    if i > 1 and sub == 0:
        print(0)
        sys.exit()
    if sub <= 2:
        continue
    sub -= 1
    count = 0
    for j in range(sub // 2 + 1):
        count += math.factorial(sub - j) // math.factorial(j) // math.factorial(sub - j * 2)
    patterns.append(count)
count = 1
for p in patterns:
    count *= p
print(count % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

print(ans[N] % (10 ** 9 + 7))
### BUGGY CODE ###

H, N = [int(i) for i in input().split()]
An = []
Bn = []
#Rn = []
for n in range(N):
  a, b = [int(i) for i in input().split()]
  An.append(a)
  Bn.append(b)
#  Rn.append(b/a)

maxA = max(An)
dp = [[1000000000 for _ in range(H+1 + maxA)] for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
  dp[n][0] = 0
  a, b = An[n], Bn[n]
  for h in range(1, H+1+maxA):
    if h >= a:
      dp[n+1][h] = min(dp[n][h-a] + b, dp[n][h], dp[n+1][h-a] + b)
    else:
      dp[n+1][h] = dp[n][h]
print(min(dp[N][H:]))
    


### FIXED CODE ###

import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

dp = np.array([0]*(H+1))

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)

print(dp[-1])
### BUGGY CODE ###

[l,r] = [int(i) for i in input().split()]

ans = 2018	
if abs(l-r) == 1:
	print(l*r%2019)

else:
	for i in range(l,r):
		for j in range(l+1,r+1):
			rem = i%2019 *j%2019
			if rem < ans:
				ans = rem

	print(ans)	

### FIXED CODE ###

L, R = list(map(int, input().split(' ')))
#print(L, R)
 
min = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        mod_ij = (i * j) % 2019
        if min > mod_ij:
            min = mod_ij
            if min == 0:
                break
    if min == 0:
        break
print(min)
### BUGGY CODE ###

target = int(input())
ans = 0
waru = 2
while target >= waru:
  if target % waru == 0:
    for i in range(2, waru + 1):
      if waru % i == 0:
        waruwaru = i
        break
    waru_copy = waru
    while waru_copy != 1:
      if waru_copy % waruwaru == 0:
        waru_copy /= waruwaru
      else:
        break
    else:
      target /= waru
      ans += 1
  waru += 1
print(ans)

### FIXED CODE ###

target = int(input())
num = target
waru = 2
exp = []
while waru ** 2 <= target and num > 1:
    rep = 0
    while num % waru == 0:
        num /= waru
        rep += 1
    waru += 1
    if rep > 0:
        exp.append(rep)
if num > 1:
    exp.append(1)
ans = 0
for item in exp:
    hiku = 1
    while item - hiku >= 0:
        item -= hiku
        ans += 1
        hiku += 1
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M = map(int,readline().split())
A = [0]+list(map(int,readline().split()))
B = list(map(int,read().split()))

N,M

for i in range(1,N):
    A[i] += A[i-1]

ticket_sum = [0]*(N*N)

# 各区間 [L,R] に対して、採用される点数を見る
for n in range(M):
    arr = B[n::M]
    # 安いチケットから入れていく -> 連結成分上で採用される
    left = list(range(N))
    right = list(range(N))
    filled = [False]*(N+1)
    for i in sorted(range(N), key=arr.__getitem__):
        filled[i] = True
        l = i if (not filled[i-1]) else left[i-1]
        r = i if (not filled[i+1]) else right[i+1]
        left[r] = l; right[l] = r
        # [l,i] x [i,r] に arr[i] を加える
        x = arr[i]
        ticket_sum[l*N+i]+=x
        if i<N-1:
            ticket_sum[(i+1)*N+i]-=x
        if r<N-1:
            ticket_sum[l*N+r+1]-=x
        if i<N-1 and r<N-1:
            ticket_sum[(i+1)*N+r+1]+=x

# 2d累積和
for i in range(N,N*N):
    ticket_sum[i] += ticket_sum[i-N]
for i in range(N*N):
    if i%N:
        ticket_sum[i] += ticket_sum[i-1]

answer = 0
for i in range(N):
    x = A[i]
    for y,t in zip(A[i:],ticket_sum[N*i+i:N*i+N]):
        happy = x-y+t
        if answer < happy:
            answer = happy

print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

INF=10**10

N,M = map(int,readline().split())
A = [0,0]+list(map(int,readline().split()))
B = [[INF]*M]+[list(map(int,line.split())) for line in readlines()]

for i in range(1,N+1):
    A[i] += A[i-1]

answer = 0
INF = 10**12
diff = [INF]+[0]*N
left = [list(range(-1,N)) for m in range(M)]
arr = [INF,2,1,2]
for i in range(1,N+1):
    for m in range(M):
        p=i; prev_val=0
        q=left[m][p]
        x = B[i][m]
        while prev_val<=x:
            diff[p] += x-prev_val
            diff[q] -= x-prev_val
            p=q; q=left[m][p]
            prev_val=B[p][m]
        left[m][i]=p
    # 出発地点ごとの収入
    ticket_sum = list(itertools.accumulate(diff[::-1]))[::-1]
    for start in range(1,i+1):
        happy = ticket_sum[start] + A[start]-A[i]
        if answer < happy:
            answer = happy

print(answer)
### BUGGY CODE ###

n, m = [int(x) for x in input().split()]

a = [int(input()) for x in range(m)]
_MOD = 1000000007

dp = [0] * (n + 1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(1,n):
    if (i + 1) in a:
        dp[i + 1] = 0
    else:
        dp[i + 1] = (dp[i] + dp[i - 1]) % _MOD

print(dp[n])

### FIXED CODE ###

n, m = [int(x) for x in input().split()]

#a = [int(input()) for x in range(m)]
a = set(int(input()) for x in range(m))
_MOD = 1000000007

dp = [0] * (n + 1)
dp[0] = 1

if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(1,n):
    if (i + 1) in a:
        dp[i + 1] = 0
    else:
        dp[i + 1] = (dp[i] + dp[i - 1]) % _MOD

print(dp[n])
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    ts = list(input())

    hands = {"r": p, "s": r, "p": s}
    ans = 0
    skip = []
    for i in range(n):
        if i in skip:
            continue

        if i+k > n-1:
            ans += hands[ts[i]]

        else:
            if ts[i] != ts[i+k]:
                ans += hands[ts[i]]
            else:
                ans += hands[ts[i]]
                skip.append(i+k)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    ts = list(input())

    hands = {"r": p, "s": r, "p": s}
    ans = 0
    skip = [0]*n
    for i in range(n):
        if skip[i] == 1:
            continue

        if i+k > n-1:
            ans += hands[ts[i]]

        else:
            if ts[i] != ts[i+k]:
                ans += hands[ts[i]]
            else:
                ans += hands[ts[i]]
                skip[i+k] = 1

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

max_score = 0
for i in range(n_zeros - k + 1):
    score = sum(ones[i:i+k+1]) + sum(zeros[i:i+k])
    if max_score < score:
        max_score = score

print(max_score)


### FIXED CODE ###

n, k = map(int, input().split())
seq = [bool(int(c)) for c in input()]

ones = []
if seq[0] is False:
    ones.append(0)
zeros = []
state = True
cnt = 0
for i, c in enumerate(seq):
    if i == 0:
        state = c
        cnt = 1
        continue

    if c == state:
        cnt += 1
    else:
        if state:
            ones.append(cnt)
        else:
            zeros.append(cnt)
        cnt = 1
        state = c

if state is True:
    ones.append(cnt)
else:
    ones.append(0)
    zeros.append(cnt)

# print(ones)
# print(zeros)

n_zeros = len(zeros)

k = min(k, n_zeros)

cum_ones = []
for i, num in enumerate(ones):
    if i == 0:
        cum_ones.append(num)
        continue
    cum_ones.append(num + cum_ones[-1])
cum_zeros = []
for i, num in enumerate(zeros):
    if i == 0:
        cum_zeros.append(num)
        continue
    cum_zeros.append(num + cum_zeros[-1])

max_score = 0
for i in range(n_zeros - k + 1):
    score = 0
    score += (cum_ones[i+k] - cum_ones[i-1]) if i > 0 else cum_ones[i+k]
    if k > 0:
        score += (cum_zeros[i+k-1] - cum_zeros[i-1]) if i > 0 else cum_zeros[i+k-1]
    if max_score < score:
        max_score = score

print(max_score)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
s = sum(A)
p = 10**20
t = 0
for i in range(n):
    t += A[i]
    p = min(p, abs(s-t*2))
    if 2*t > sum(A):
        break
print(p)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
s = sum(A)
p = 10**20
t = 0
for i in range(n):
    t += A[i]
    p = min(p, abs(s-t*2))
print(p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,X,Y=map(int,input().split())
    X-=1
    Y-=1
    
    d=[[INF]*N for _ in range(N)]
    for i in range(N-1):
        d[i][i+1]=1
        d[i+1][i]=1
    d[X][Y]=1
    d[Y][X]=1
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    ans=[0]*N
    for i in range(N-1):
        for j in range(i+1,N):
            ans[d[i][j]]+=1
    for row in ans[1:]:
        print(row)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,X,Y=map(int,input().split())
    X-=1
    Y-=1
    ans=[0]*N
    for i in range(N-1):
        for j in range(i+1,N):
            ans[min(j-i,abs(X-i)+1+abs(Y-j),abs(X-j)+1+abs(Y-i))]+=1
    for row in ans[1:]:
        print(row)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    while parent[a] != a:
        a = parent[a]
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n, m = [int(i) for i in sys.stdin.readline().split()]
parent = [i for i in range(n)]

def unite(a, b):
    root_a = find_root(a)
    parent[a] = root_a
    root_b = find_root(b)
    parent[b] = root_b
    if root_a != root_b:
        parent[root_b] = root_a

def find_root(a):
    ls = []
    while parent[a] != a:
        ls.append(a)
        a = parent[a]
    for l in ls:
        parent[l] = a
    return a


for i in range(m):
    x, y, z = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    unite(x, y)

_set = set()
for i in range(n):
    _set.add(find_root(i))
print(len(_set))
### BUGGY CODE ###

N=int(input())
S=str(input())


count=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k] and j-i != k-j:
        count+=1
print(count)

### FIXED CODE ###

N=int(input())
S=str(input())
ans=S.count('R')*S.count('G')*S.count('B')

for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i]==S[j]:
      continue
    if 2*j - i < N:
      if S[2*j - i] != S[i] and S[2*j - i] != S[j]:
        ans-=1
print(ans)
### BUGGY CODE ###

import sys

N, W = map(int, input().split())

WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

dp = [[0]*(N+1) for i in range(W+1)]
for i in range(1, W+1):
        for j in range(1, N+1):
                if i - WV[j-1][0]>=0:
                        dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = dp[i][j-1]

print(dp[W][N])


### FIXED CODE ###

import sys
 
N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
        w[i], v[i] = map(int, sys.stdin.readline().split())
 
#WV = [list(map(int, sys.stdin.readline().split())) for i in range(N)]
 
 
dp = [[0]*(N+1) for j in range(W+1)]
 
for i in range(1, W+1):
        for j in range(1, N+1):
                if i - w[j-1]>=0:
                #if i - WV[j-1][0]>=0:
                        dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1], dp[i][j-1])
                        #dp[i][j] = max(dp[i-WV[j-1][0]][j-1]+WV[j-1][1], dp[i][j-1])
                else:
                        dp[i][j] = dp[i][j-1]
 
print(dp[W][N])
### BUGGY CODE ###

import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from pandas import DataFrame

k = raw_input()
n = raw_input()
a = [int(i) for i in n.split()]
a.sort()

sum1 = 0
for i in range(int(k)):
    sum1 += min(a[2*i], a[2*i+1])
    print sum1

### FIXED CODE ###

k = raw_input()
n = raw_input()
a = [int(i) for i in n.split()]
a.sort()

sum1 = 0
for i in range(int(k)):
    sum1 += min(a[2*i], a[2*i+1])
print sum1
### BUGGY CODE ###

MOD = 10 ** 9 + 7
INF = 10  ** 7
def main():
    n,a,b = map(int,input().split())
    m = n//2
    Chemical = [tuple(map(int,input().split())) for _ in range(n)]
    Chemical1 = Chemical[:m]
    Chemical2 = Chemical[m:]
    Sum1 = [[INF] * 405 for _ in range(405)]
    Sum2 = [[INF] * 405 for _ in range(405)]
    for bit in range(1<<m):
        cost,v1,v2 = 0,0,0
        for i in range(m):
            if (bit>>i)&1:
                d,e,f = Chemical1[i]
                v1 += d
                v2 += e
                cost += f
        Sum1[v1][v2] = min(Sum1[v1][v2],cost)
    
    for bit in range(1<<(n - m)):
        cost,v1,v2 = 0,0,0
        for i in range(n - m):
            if (bit>>i)&1:
                d,e,f = Chemical2[i]
                v1 += d
                v2 += e
                cost += f
        Sum2[v1][v2] = min(Sum2[v1][v2],cost)
    
    ans = INF
    for i in range(405):
        for j in range(405):
            if Sum1[i][j] != INF:
                C = Sum1[i][j]
                k = max((i + a - 1)//a,(j + b - 1)//b,1)
                while k * a - i < 405 and k*b - j < 405:
                    if Sum2[k*a - i][k*b - j] != INF:
                        ans = min(ans,Sum2[k*a - i][k*b - j] + C)
                    k += 1
    print(ans if ans != INF else -1)
if __name__ == '__main__':
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10  ** 7
def main():
    n,a,b = map(int,input().split())
    m = n//2
    Chemical = [tuple(map(int,input().split())) for _ in range(n)]
    Chemical1 = Chemical[:m]
    Chemical2 = Chemical[m:]
    Sum1 = [[INF] * 405 for _ in range(405)]
    Sum2 = [[INF] * 405 for _ in range(405)]
    for bit in range(1<<m):
        cost,v1,v2 = 0,0,0
        for i in range(m):
            if (bit>>i)&1:
                d,e,f = Chemical1[i]
                v1 += d
                v2 += e
                cost += f
        Sum1[v1][v2] = min(Sum1[v1][v2],cost)
    
    for bit in range(1<<(n - m)):
        cost,v1,v2 = 0,0,0
        for i in range(n - m):
            if (bit>>i)&1:
                d,e,f = Chemical2[i]
                v1 += d
                v2 += e
                cost += f
        Sum2[v1][v2] = min(Sum2[v1][v2],cost)
    
    ans = INF
    for i in range(405):
        for j in range(405):
            if Sum1[i][j] != INF:
                C = Sum1[i][j]
                k = max((i + a - 1)//a,(j + b - 1)//b,1)
                while k * a - i < 405 and k*b - j < 405:
                    if Sum2[k*a - i][k*b - j] != INF:
                        ans = min(ans,Sum2[k*a - i][k*b - j] + C)
                    k += 1
    print(ans if ans != INF else -1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = int(input())

for i in range(1, int(s**0.5)+1)[::-1]:
    if s%i == 0:
        x = i
        y = s//i
        break

print(0, 0, 0, x, y, 0)

### FIXED CODE ###

s = int(input())

x1 = 10**9
y1 = 1
x2 = (10**9 - s%10**9)%10**9
y2 = (s+x2) // 10**9

print(0, 0, x1, y1, x2, y2)