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

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
from functools import lru_cache
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

class Angle():
    DIAGONAL = 0
    UP = 1
    LEFT = 2

s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
class node():
    def __init__(self):
        self.value = 0
        # self.angle = None
        self.ans=""
dp = [[node() for j in range(m+1)] for i in range(n+1)]
# for i in range(1,n + 1):
#     dp[i][0].angle = Angle.UP
# for j in range(1,m + 1):
#     dp[0][j].angle = Angle.LEFT
for i in range(n):
    for j in range(m):
        same = dp[i][j].value + 1 if s[i] == t[j] else -1
        up = dp[i][j+1].value
        left = dp[i+1][j].value
        option = [same, up, left]
        max_index = option.index(max(option))
        dp[i + 1][j + 1].value = max(option)
        # dp[i + 1][j + 1].angle = max_index
        if max_index == Angle.DIAGONAL:
            dp[i + 1][j + 1].ans = dp[i][j].ans + s[i]
        elif max_index == Angle.LEFT:
            dp[i + 1][j + 1].ans = dp[i + 1][j].ans
        else:
            dp[i + 1][j + 1].ans = dp[i][j+1].ans

            
# print(dp[n][m].value)
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].value,end="")
#     print("")
# print("")
# print("")
# for i in range(n+1):
#     for j in range(m+1):
#         print(dp[i][j].ans,end="")
#     print("")
print(dp[n][m].ans)

        

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

from collections import deque
import copy

n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)

### FIXED CODE ###

from collections import deque
import copy, sys

input = sys.stdin.readline
n = int(input())
a = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(n)]
q = deque()
pre_q = deque()
day = 0

def check(p, q):
    if not len(a[p]):
        return
    o = a[p][0]
    if p == a[o][0]:
        if p > o: p, o = o, p
        if not (p, o) in q:
            q.append((p, o))

fin = []
for p in range(n):
    if not p in fin:
        o = a[p][0]
        if p == a[o][0]:
            q.append((p, o))
            fin += [p, o]

while q:
    day += 1
    pre_q = copy.copy(q)
    q.clear()
    for (p, o) in pre_q:
        a[p].popleft()
        a[o].popleft()
        check(p, q)
        check(o, q)

if all(map(len, a)):
    print(-1)
else:
    print(day)
### BUGGY CODE ###

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

def lcs(a, b):
    L = []
    for bk in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(L):
            chr_idx = a.find(bk, bgn_idx) + 1
            if not chr_idx:
                break
            L[i] = min(cur_idx, chr_idx)
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(bk, bgn_idx) + 1
            if chr_idx:
                L.append(chr_idx)
    return len(L)

ans = 0
for i in range(N):
    ans = max(ans, lcs(S[:i+1], S[i+1:]))

print(ans)


### FIXED CODE ###

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

maxL = 0

for i in range(1, N-1):
    cnt = 0
    left = 0
    for j in range(0, N-i):
        if S[j]==S[j+i]:
            cnt+=1
            if maxL < cnt:
                maxL = cnt
            if cnt == i:
                break
        else:
            cnt = 0
            left = j + 1

print(maxL)
### BUGGY CODE ###

N,M = map(int,input().split())
a = [0]*M
b = [0]*M
c = [[] for _ in range(M)]
for i in range(M):
    a[i],b[i] = map(int,input().split())
    c[i] = list(map(int,input().split()))
    
inf = 2**30 - 1
dp = [[inf]*(2**N+1) for _ in range(M+1)]
dp[0][0] = 0

c_bit = [0] * M
for i in range(M):
    for t in c[i]:
        c_bit[i] += 1<<(t-1)

for i in range(M):
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][j|c_bit[i]] = min(dp[i+1][j|c_bit[i]],dp[i][j]+a[i])

ans = dp[M][(1<<N)-1]
if ans==inf:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
a = [0]*M
b = [0]*M
c = [[] for _ in range(M)]
for i in range(M):
    a[i],b[i] = map(int,input().split())
    c[i] = list(map(int,input().split()))
    
inf = 2**30 - 1
dp = [[inf]*(2**N+1) for _ in range(M+1)]
dp[0][0] = 0

c_bit = [0] * M
for i in range(M):
    for t in c[i]:
        c_bit[i] += 1<<(t-1)

for i in range(M):
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        dp[i+1][j|c_bit[i]] = min(dp[i+1][j|c_bit[i]],dp[i][j]+a[i])

ans = dp[M][(1<<N)-1]
if ans==inf:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = 1
for i in range(1,n):
    for j in range(2,n):
        if i**j <= n:
            a = max(a,i**j)
print(a)

### FIXED CODE ###

n = int(input())
a = 1
for i in range(1,n):
    for j in range(2,n):
        if i**j <= n:
            a = max(a,i**j)
        else:
            break


print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
sub = []

for i in range(N):
    sub.append(A.count(i+1))

for i in range(len(sub)):
    print(sub[i])

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))

sub = np.bincount(A, weights=None, minlength=N+1)

for i in range(N):
    print(sub[i+1])
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N):
  ans += i
print(ans)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

from itertools import product
from collections import deque
from copy import deepcopy

def state_brute_force(state, count):
    state_list = [state for _ in range(count)]
    for s in product(*state_list):
        yield s


N, K = map(int, input().split())
D = list(map(int, input().split()))

ans = 0

pop_l = deque.popleft
pop_r = deque.pop
add_l = deque.appendleft
add_r = deque.append

stop_condition = sum([item for item in D if item > 0])

cache = {}

for cmb in state_brute_force([pop_l, pop_r, add_l, add_r], K):
    q = deque(D)
    now = []
    op_counter = 0
    value = 0
    operations = []
    for operation in cmb:
        operations.append(operation)
        ca = cache.get(tuple(operations))
        if ca is not None:
            q = deque(ca[0])
            now = deepcopy(ca[1])
            continue
        if operation == add_l or operation == add_r:
            if len(now) == 0:
                break
            item = min(now)
            now.remove(item)
            operation(q, item)
        if operation == pop_l or operation == pop_r:
            if len(q) == 0:
                break
            now.append(operation(q))
    cache[tuple(operations)] = (list(q), now)
    value = max(value, sum(now))
    ans = max(ans, value)
    if ans == stop_condition:
        break

print(ans)




### FIXED CODE ###

N, K = map(int, input().split())
D = list(map(int, input().split()))

ans = 0

for left in range(K + 1):
    for right in range(K - left + 1):
        if left + right > N:
            break
        items = list(D[0:left])
        items.extend(D[::-1][0:right])
        dis = K - (left + right)
        i = 0
        items = sorted(items, reverse=True)
        while True:
            ans = max(ans, sum(items))
            if i < dis and len(items) > 0:
                i += 1
                items.pop()
                continue
            else:
                break

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

from bisect import bisect_right
n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
cnt = 0
bn = []
for i in range(n):
    x2 = bisect_right(c, b[i])
    bn.append(n-x2)
for i in range(n):
    x1 = bisect_right(b, a[i])
    cnt += sum(bn[x1:])
print(cnt)

### FIXED CODE ###

from bisect import bisect_right
from bisect import bisect_left

n = int(input())
a = sorted(map(int, input().split()))
b = sorted(map(int, input().split()))
c = sorted(map(int, input().split()))
cnt = 0
bn = []
for i in range(n):
    x1 = bisect_left(a, b[i])
    x2 = bisect_right(c, b[i])
    cnt += x1*(n-x2)
print(cnt)
### BUGGY CODE ###

#import numpy as np

N = int(input())
Alist = list(map(int,input().split()))

#ans = np.prod(Alist)
Alist.sort()
ans = 1
for i in range(N):
  #print (Alist[i])
  ans*= Alist[i]
  if Alist[i]==0:
    break

if ans >10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

num = int(input())
numbers = list(map(int,input().split()))
sum = 1
for i in range(num):
  sum *=numbers[i]
  if (sum>(10**18)):
    sum = -1
    break
if 0 in numbers:
  sum = 0
print (sum)
### BUGGY CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
b, c = [list(i) for i in zip(*bc)]

sum_b = sum(b)

for i in range(m):
    add = [c[i] for _ in range(b[i])]
    a.extend(add)
a.sort()
a = a[sum_b:]


print(sum(a))

### FIXED CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
bc = [list(map(int,input().split())) for i in range(m)]
bc = sorted(bc, key = lambda x : x[1], reverse=True)

sum_b = 0
for b, c in bc:
    sum_b += b
    a += [c] * b
    if n < sum_b:
        break
a.sort(reverse=True)
a = a[:n]

print(sum(a))
### BUGGY CODE ###

inf = input().split()
N = int(inf[0])
Q = int(inf[1])
S = input()
ans = []
for i in range(Q):
  inf = input().split()
  l = int(inf[0])-1
  r = int(inf[1])
  ans += [(S[l:r].count('AC'))]
for a in ans:
  print(a)
  

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t= [0]*(N+1)
for i in range(N):
  t[i+1] = t[i] +(1 if S[i:i+2]=='AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1]-t[l-1])
### BUGGY CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}
isChecked = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
X = []
g = 0
i = 1
while len(X) != N:
    if isChecked[i]:
        i += 1
        continue
    isChecked[i] = 1
    group_id[i] = g
    x = [i]
    ch = child[i].copy()
    while ch:
        c = ch.pop(0)
        group_id[c] = g
        isChecked[c] = 1
        x.append(c)
        ch = list(set(ch) | set(child[c]) - set(x))        
    group[g] = len(x)
    X += x
    g += 1
    i += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1
        
print(*ans[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])
### BUGGY CODE ###

## dijkstraで解く

from collections import deque
import heapq

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1 << 50
N = 10**4
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = []

heapq.heappush(q,(0, (ch-1)*N+(cw-1)))
while q:
    cnt, n  = heapq.heappop(q)
    h,w = divmod(n, N)
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    # 歩いた
    for dh in range(-2,3):
        for dw in range(-2,3):            
            hn = h + dh
            wn = w + dw

            if not 0 <= wn < W: continue
            if not 0 <= hn < H: continue
            if fs[hn][wn] == "#": continue
            if dps[hn][wn] != INF:continue
            if abs(dh) + abs(dw) <= 1:
                heapq.heappush(q, (cnt, hn*N+wn))
            else:
                heapq.heappush(q, (cnt+1, hn*N+wn))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

fs = []
for i in range(H):
    r = list(input())
    fs.append(r)

walks = [(-1,0),(1,0),(0,1),(0,-1)]
magics = []
for i in range(-2,3):
    for j in range(-2,3):
        if i==j==0:continue
        if (i,j) not in walks:
            magics.append((i,j))

INF = 1 << 50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
q = deque([])
q.appendleft((ch-1,cw-1,0))
while len(q)>0:
    h,w,cnt = q.popleft()
    if cnt > dps[h][w]:continue
    dps[h][w] = cnt
    for dh, dw in walks:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.appendleft((hn, wn, cnt))
    for dh, dw in magics:
        hn = h + dh
        wn = w + dw
        if 0<=hn<H and 0<=wn<W:
            if dps[hn][wn] != INF:continue
            if fs[hn][wn] == ".":
                q.append((hn, wn, cnt+1))

ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)
### BUGGY CODE ###


N, K = map(int, input().split())
key_data_list = []
for _ in range(K):
    value, op = map(int, input().split())
    open_boxes = map(int, input().split())
    box_value = 0
    for opb in open_boxes:
      box_value += 2**(opb-1)
    key_data_list.append([value, box_value])

import numpy as np

max_tresure_state = 2**N
max_key_price = 2**30
dp_table = np.full((K+1,max_tresure_state),max_key_price)

dp_table[0][0] = 0

for key_index in range(K):
    for tresure_state in range(max_tresure_state):
        key_value = key_data_list[key_index][0]
        key_state = key_data_list[key_index][1]

        if dp_table[key_index+1][tresure_state] > dp_table[key_index][tresure_state]:
            dp_table[key_index+1][tresure_state] = dp_table[key_index][tresure_state]

        buying_state = key_state | tresure_state
        dp_table[key_index+1][buying_state] = min(dp_table[key_index][buying_state],
                                                  dp_table[key_index+1][buying_state],
                                                  dp_table[key_index][tresure_state] + key_value)


result_value = dp_table[K][max_tresure_state-1]
if result_value == max_key_price:
    print(-1)
else:
    print(int(result_value))


### FIXED CODE ###


N, K = map(int, input().split())
key_data_list = []
for _ in range(K):
    value, op = map(int, input().split())
    open_boxes = map(int, input().split())
    box_value = 0
    for opb in open_boxes:
      box_value += 2**(opb-1)
    key_data_list.append([value, box_value])

max_tresure_state = 2**N
max_key_price = 2**30
dp_table = [[max_key_price] * (max_tresure_state) for i in range(K+1)]

dp_table[0][0] = 0

for key_index in range(K):
    for tresure_state in range(max_tresure_state):
        key_value = key_data_list[key_index][0]
        key_state = key_data_list[key_index][1]

        if dp_table[key_index+1][tresure_state] > dp_table[key_index][tresure_state]:
            dp_table[key_index+1][tresure_state] = dp_table[key_index][tresure_state]

        buying_state = key_state | tresure_state
        dp_table[key_index+1][buying_state] = min(dp_table[key_index][buying_state],
                                                  dp_table[key_index+1][buying_state],
                                                  dp_table[key_index][tresure_state] + key_value)


result_value = dp_table[K][max_tresure_state-1]
if result_value == max_key_price:
    print(-1)
else:
    print(int(result_value))
### BUGGY CODE ###

from itertools import product
from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    heappush(heap, (0, s))
    while heap:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]:
            continue
        dist[v] = d
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(product([0], range(1, n+1))) + list(product([1], range(1, n+1)))
E = defaultdict(dict)
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E[(0, u)][(0, v)] = a
    E[(0, v)][(0, u)] = a
    E[(1, u)][(1, v)] = b
    E[(1, v)][(1, u)] = b
ans = [MON]*n
for i in reversed(range(n)):
    E[(0, i+1)][(1, i+1)] = 0
    dist = dijkstra(V, E, (0, s))
    ans[i] -= dist[(1, t)]
print(*ans, sep='\n')

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop

def dijkstra(V, E, s):
    '''
    Input:
        V = list(range(N))
        E = defaultdict(dict)
        s (in V) : start vertex
    Output:
        dist: the list of the minimum cost from s to arbitrary vertex v in the given graph
    '''
    INF = float('inf')
    dist = {v: INF for v in V}
    heap = []
    dist[s] = 0; rem = len(V);
    heappush(heap, (0, s))
    while heap and rem:
        d, v = heappop(heap)
        # don't need to check when the stored value is greater than provisional distance
        if d > dist[v]: continue
        rem -= 1;
        for u, c in E[v].items():
            temp = d + c
            if temp < dist[u]:
                dist[u] = temp
                heappush(heap, (temp, u))
    return dist

MON = 10**15
n, m, s, t = map(int, input().split())
V = list(range(1, n+1))
E1, E2 = {v: {} for v in V}, {v: {} for v in V}
for _ in range(m):
    u, v, a, b = map(int, input().split())
    E1[u][v] = a
    E1[v][u] = a
    E2[u][v] = b
    E2[v][u] = b
ans = [MON]*n
dist_yen = dijkstra(V, E1, s)
dist_snuuk = dijkstra(V, E2, t)
temp = float('inf')
for v in V[::-1]:
    temp = min(temp, dist_yen[v] + dist_snuuk[v])
    ans[v-1] -= temp
print(*ans, sep='\n')
### BUGGY CODE ###

import math
from queue import Queue

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

root = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m):
    a, b = [int(i) for i in input().split()]
    root[a][b] = 1
    root[b][a] = 1


check = [0 for _ in range(n+1)]
check[1] = 1

q = Queue()
q.put(1)

while ( not q.empty() ):
    now = q.get()
    for i in range(1,n+1):
        if(root[now][i] == 1 and check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n+1):
    if(check[i] == 0):
        flag = 0

if(flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")



### FIXED CODE ###

import math
from queue import Queue

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

root = [[] for _ in range(n+1)]

for i in range(m):
    a, b = [int(i) for i in input().split()]
    root[a].append(b)
    root[b].append(a)

check = [0 for _ in range(n + 1)]
check[1] = 1

q = Queue()
q.put(1)

while (not q.empty()):
    now = q.get()
    for i in root[now]:
        if (check[i] == 0):
            check[i] = now
            q.put(i)

flag = 1
for i in range(2, n + 1):
    if (check[i] == 0):
        flag = 0

if (flag == 1):
    print("Yes")
    for j in range(2, n + 1):
        print(check[j])
else:
    print("No")
### BUGGY CODE ###

a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

result = []

max_weight = a[1]

def calc(i, queue):
    if len(b) <= i:
        return

    current = b[i]
    prev = queue[-1] if 0 < len(queue) else [0, 0] 
    
    if current[0] + prev[0] <= max_weight:
        result.append(prev[1] + current[1])
    
    next_queue = queue[:]
    next_queue.append([prev[0] + current[0], prev[1] + current[1]])
    calc(i + 1, next_queue)
    calc(i + 1, queue)

calc(0, [])

print(max(result))

### FIXED CODE ###

a = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(a[0])]

max_index = a[0]
max_weight = a[1]

dp = [ [0] * (max_weight + 1) for j in range(max_index + 1)]

def solve():
    for i in range(max_index - 1, -1, -1):
        for j in range(max_weight + 1):
            if (j < b[i][0]):
                dp[i][j] = dp[i + 1][j]
            else:
                dp[i][j] = max([dp[i + 1][j], dp[i + 1][j - b[i][0]] + b[i][1]])
    print(dp[0][max_weight])

solve()