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

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

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    cnt = min(K, i)
    for j in range(cnt):
        compare.append(dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = min(compare)

print(dp[-1])


### FIXED CODE ###

import heapq
N, K  = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, N):
    compare = []
    heapq.heapify(compare)
    cnt = min(K, i)
    for j in range(cnt):
        heapq.heappush(compare, dp[i-j-1] + abs(h[i]-h[i-j-1]))
    dp[i] = heapq.heappop(compare)

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

import itertools

n = int(input())
strs = [str(input()) for _ in range(n)]

cnt = 0
while len(strs) != 0:
  s = strs.pop()
  for anagram in set(itertools.permutations(s)):
    if "".join(anagram) in strs:
      cnt += 1
      
print(cnt)


### FIXED CODE ###

n = int(input())
strs = ["".join(sorted(str(input()))) for _ in range(n)]

cache = {}
cnt = 0
for s in strs:
  if s in cache.keys():
    cnt = cnt + cache[s]
    cache[s] = cache[s] + 1
  else:
    cache[s] = 1
print(cnt)
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
k = 1
flag = 0
for i in range(n):
  lst2 = list(map(lambda x: x-lst[i], lst))
  lst2.pop(i)
  for j in lst2:
    k *= j
  if k == 0:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')

### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
flag = 0
lst.sort()
for i in range(n-1):
  if lst[i] == lst[i+1]:
    print('NO')
    flag = 1
    break
if flag == 0:
  print('YES')
### BUGGY CODE ###

#coding:utf-8
import numpy as np
def argsort_p1(ls):
    a = sorted(ls)
    r = [a.index(t)+1 for t in ls]
    return r

N,M = list(map(int,input().split()))
P = []
Y = []
for m in range(M):
    p,y = list(map(int,input().split()))
    P.append(p)
    Y.append(y)
#print (P,Y)
ls = [ [] for _ in range(max(P))]
#print (ls)
for p,y in zip(P,Y):
    ls[p-1].append(y)
ls_dict = []
for line in ls:
    #arg_line = np.argsort(line)+1
    arg_line = argsort_p1(line)
    temp_dict = dict(zip(line, arg_line))
    ls_dict.append(temp_dict)
#print (ls_dict)
for p,y in zip(P,Y):
    print (str(p).zfill(6)+str(ls_dict[p-1][y]).zfill(6))


### FIXED CODE ###

N, M = map(int,input().split())
ls = []
for m in range(M):
    p, y = map(int,input().split())
    ls.append([p,y])
sorted_ls = sorted(ls,key=lambda x:x[1])
counter = [0 for i in range(N+1)]
d = {}
for p,y in sorted_ls:
    counter[p]+=1
    num = counter[p]
    d[y] = num
for p,y in ls:
    #print (p,d[y])
    print (str(p).zfill(6)+str(d[y]).zfill(6))
### BUGGY CODE ###

N, M = map(int, input().strip().split())

for i in range(M//N,0,-1):
    if M%i==0:
        print(i)
        break

### FIXED CODE ###

import math
N, M = map(int, input().strip().split())
st= min(M//N,int(math.sqrt(M)))
cand=0
if M//N <= int(math.sqrt(M)):
    for i in range(M//N,0,-1):
        if M%i==0:
            print(i)
            break
else:
    for i in range(1,int(math.sqrt(M)),1):
        if M%i==0:
            if M//N >= i:
                cand=max(cand,i)
            if M//N >= M//i:
                cand=max(cand,M//i)
    print(cand)
### BUGGY CODE ###

S = input()
N = int(input())
Q = tuple([_ for _ in input().split()] for _ in range(N))

def move(s, q):
    if q[0] == "1":
        return s[::-1]
    else:
        if q[1] == "1":
            return q[2] + s
        else:
            return s + q[2]
        
for q in Q:
    S = move(S, q)
print(S)

### FIXED CODE ###

S = input()
N = int(input())
Q = tuple([_ for _ in input().split()] for _ in range(N))
C = 0
F = ""
R = ""
for q in Q:
    if q[0] == "1":
        C = (C+1)%2
    else:
        if (int(q[1])+C)%2 != 0:
            F = q[2] + F
        else:
            R = R + q[2]
S = F + S + R
if C != 0:
    S = S[::-1]
print(S)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
print(*[l.index(i+1)+1 for i in range(n)])

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))

ll = []
for i, j in enumerate(l):
  ll.append([i+1, j])
ll.sort(key=lambda x:x[1])

la = []
for i in range(n):
  la.append(ll[i][0])

print(*la)
### BUGGY CODE ###

import heapq
def dijkstra(graph, size, start, r):
    distance = [float('inf')] * size
    distance[start] = 0
    que = []
    heapq.heappush(que, (0, start))
    while len(que):
        _, u = heapq.heappop(que)
        for length, vi in graph[u]:
            if distance[vi] > distance[u] + length[r]:
                distance[vi] = distance[u] + length[r]
                heapq.heappush(que, (distance[vi], vi))
    return distance

import sys
f = sys.stdin

import collections

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [list(map(int, f.readline().split())) for _ in range(n)]
    graph = collections.defaultdict(list)
    for ai, bi, cost, time in abct:
        graph[ai].append(((cost, time), bi))
        graph[bi].append(((cost, time), ai))
        
    k = int(f.readline())
    
    dist = {}
    for i in range(k):
        p, q, r = map(int, f.readline().split())
        
        if (q,r) in dist:
            p, q = q, p
        elif (p,r) not in dist:
            dist[(p,r)] = dijkstra(graph, m + 1, p, r)
        print(dist[(p,r)][q])

### FIXED CODE ###

import heapq
import sys
from collections import defaultdict

def dijkstra(graph, size, start):
    d = [float('inf')] * size
    d[start] = 0
    q = [(0, start)]
    while len(q):
        du, u = heapq.heappop(q)
        for length, v in graph[u]:
            if d[v] > du + length:
                d[v] = du + length
                heapq.heappush(q, (d[v], v))
    return d

f = sys.stdin

while True:
    n, m = map(int, f.readline().split())
    if n == 0:
        break
    abct = [map(int, f.readline().split()) for _ in range(n)]
    d = [defaultdict(list), defaultdict(list)]
    
    for ai, bi, ci, ti in abct:
        ai -= 1
        bi -= 1
        d[0][ai].append((ci, bi))
        d[0][bi].append((ci, ai))
        d[1][ai].append((ti, bi))
        d[1][bi].append((ti, ai))
    
    dist = {}
    for i in range(int(f.readline())):
        p, q, r = map(int, f.readline().split())
        p -= 1
        q -= 1
        try:
            print(dist[(q,r)][p])
        except KeyError:
            try:
                print(dist[(p,r)][q])
            except:
                dist[(p,r)] = dijkstra(d[r], m, p)
                print(dist[(p,r)][q])
### BUGGY CODE ###


N = int(input())
p_list = [int(x) for x in input().strip().split()]

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat *= sum + 1
    if r_pos >= 2 * sum + 1:
        sum += 1

print(pat % 1000000007)

### FIXED CODE ###

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

pat = 1
sum = 0
for i, r_pos in enumerate(p_list):
    pat = (pat * (sum + 1)) % 1000000007
    if r_pos >= 2 * sum + 1: sum += 1
print(pat)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    c = 0
    for kk in range(k):
        h, l = 0, 0
        for ai in a:
            if ai // 2**kk % 2:
                h += 1
            else:
                l += 1
        kc = h * l * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    c = 0
    for kk in range(k):
        h, l = 0, 0
        for ai in a:
            if ai // 2**kk % 2:
                h += 1
            else:
                l += 1
        kc = h * l * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

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

k, a, b = map(int, input().split())
maisu = 1
if b - a <= 2:
    maisu += k
else:
    while True:
        if k >= 2 and maisu >= a:
            maisu += b-a
            k -= 2
        else:
            k-= 1
            maisu += 1
        if k == 0:
            break
print(maisu)

### FIXED CODE ###

k, a, b = map(int, input().split())
maisu = 1
if b - a <= 2:
    maisu += k
else:
    cc = (k - (a-1))//2
    maisu += (b-a)*cc
    maisu += k-2*cc
print(maisu)
### BUGGY CODE ###

n,c = map(int,input().split())

x = []
v = []
array1 = []
array2 = []

for i in range(n):
  a,b = map(int, input().split())
  x.append(a)
  v.append(b)
  
rx = []
rv = []
for i in reversed(range(len(x))):
  rx.append(c-x[i])
  rv.append(v[i])
  
count = x[0]
array1.append(v[0] - x[0])
for i in range(1,n):
  array1.append(v[i]-x[i]+array1[i-1]+count)
  count = x[i]
  
count = rx[0]
array2.append(rv[0] - rx[0])
for i in range(1,n):
  array2.append(rv[i]-rx[i]+array2[i-1]+count)
  count = rx[i]
  
ans = 0
for i in range(n):
  if i != n-1:
    tmp = max(array1[i], array1[i]-x[i]+max(array2[:n-i-1]))
    ans = max(ans, tmp)
  else:
    ans = max(ans, array1[i])
  
for i in range(n):
  if i != n-1:
    tmp = max(array2[i], array2[i]-rx[i]+max(array1[:n-i-1]))
    ans = max(ans, tmp)
  else:
    ans = max(ans, array2[i])
    

  
print(ans)

### FIXED CODE ###

n,c = map(int,input().split())

x = []
v = []
array1 = []
array2 = []

for i in range(n):
  a,b = map(int, input().split())
  x.append(a)
  v.append(b)
  
rx = []
rv = []
for i in reversed(range(len(x))):
  rx.append(c-x[i])
  rv.append(v[i])
  
count = x[0]
array1.append(v[0] - x[0])
for i in range(1,n):
  array1.append(v[i]-x[i]+array1[i-1]+count)
  count = x[i]
  
count = rx[0]
array2.append(rv[0] - rx[0])
for i in range(1,n):
  array2.append(rv[i]-rx[i]+array2[i-1]+count)
  count = rx[i]

num = 0
max_array = []
for i in range(len(array1)-1):
  num = max(num, array1[i])
  max_array.append(num)

max_array = list(reversed(max_array))

num = 0
rmax_array = []
for i in range(len(array2)-1):
  num = max(num, array2[i])
  rmax_array.append(num)
  
rmax_array = list(reversed(rmax_array))
  
  
ans = 0
for i in range(n):
  if i != n-1:
    tmp = max(array1[i], array1[i]-x[i]+rmax_array[i])
    ans = max(ans, tmp)
  else:
    ans = max(ans, array1[i])
  
for i in range(n):
  if i != n-1:
    tmp = max(array2[i], array2[i]-rx[i]+max_array[i])
    ans = max(ans, tmp)
  else:
    ans = max(ans, array2[i])
    
print(ans)
### BUGGY CODE ###

def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    prev = [[0] * 4 for _ in range(C+1)]
    for r in range(1, R+1):
        cur = [[0] * 4 for _ in range(C+1)]
        for c in range(1, C+1):
            cur[c][0] = max(prev[c][0], cur[c-1][0])
            for i in range(1, 4):
                cur[c][i] = max(prev[c][i], cur[c-1][i], prev[c][3]+G[r][c], cur[c-1][i-1]+G[r][c])
        prev = deepcopy(cur)
        # print(prev)

    print(max(cur[-1]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    from copy import deepcopy
    input = sys.stdin.readline
    R, C, K = [int(x) for x in input().strip().split()]
    G = [[0] * (C+1) for r in range(R+1)]
    for k in range(K):
        r, c, v = [int(x) for x in input().strip().split()]
        G[r][c] = v
    # for r in range(R+1):
    #     print(G[r])
    ans = [[[0] * 4 for _ in range(C+1)] for _ in range(2)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            ans[r%2][c][0] = max(ans[(r-1)%2][c][-1], ans[r%2][c-1][0])
            for i in range(1, 4):
                ans[r%2][c][i] = max(ans[(r-1)%2][c][3], ans[r%2][c-1][i], ans[(r-1)%2][c][3]+G[r][c], ans[r%2][c-1][i-1]+G[r][c])

    print(max(ans[R%2][-1]))

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

import bisect
import numpy as np
import scipy as sp
from sys import stdin

r, g, b, n = map(int, input().split())
count = 0

for i in range(n + 1):
    for j in range(n + 1):
        total = n - r * i - g * j
        if total < 0:
            break
        if total % b == 0:
            count += 1

print(count)


### FIXED CODE ###



r, g, b, n = map(int, input().split())
count = 0

for i in range(n + 1):
    for j in range(n + 1):
        total = n - r * i - g * j
        if total < 0:
            break
        if total % b == 0:
            count += 1

print(count)
### BUGGY CODE ###

n,k,q=map(int,input().split())
l=[k]*n
for i in range(q):
    a=int(input())
    for j in range(n):
        l[j]-=1
        if j==a-1:
            l[j]+=1
for k in l:
    if k>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
l=[k-q]*n
for i in range(q):
    a=int(input())
    l[a-1]+=1
for k in l:
    if k>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()

memo = defaultdict(str)
def rec(S):
    if memo[S] != '':
        return memo[S]
    N = len(S)
    res = True
    S = list(S)
    for i in range(1, N-1):
        if S[i-1] != S[i+1]:
            tmp = S.pop(i)
            res &= rec(''.join(S))
            S.insert(i, tmp)
    if res:
        memo[''.join(S)] = False
        return False
    else:
        memo[''.join(S)] = True
        return True

if rec(S):
    print('First')
else:
    print('Second')


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc064/editorial.pdf
・最終的には両端にある2種類の文字か、両端が同じ文字ならそれとそれ以外のもう1文字以外は残らない。
・なので残った文字数の偶奇は分かる。
・そこから総ターン数が分かるので、その偶奇で勝敗が分かる。
"""

import sys
from collections import deque, Counter, defaultdict
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, product, combinations, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial

def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

S = input()
N = len(S)

if S[0] == S[-1]:
    if N % 2 == 0:
        print('First')
    else:
        print('Second')
else:
    if N % 2 == 0:
        print('Second')
    else:
        print('First')
### BUGGY CODE ###

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

s = sum(a)

for i in range(q):
    cnt = 0
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
            cnt += 1
    s += (c-b)*cnt
    print(s)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)

ad = collections.Counter(a)

for i in range(q):
    b, c = map(int, input().split())
    s += ad.get(b, 0) * (c - b) 
    print(s)
    ad[c] += ad.get(b, 0)
    ad[b] = 0
### BUGGY CODE ###

# ABC134E

import sys
from bisect import bisect_left
input=sys.stdin.readline

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=len(lbds)-bisect_left(lbds[::-1],A[i])
            lbds[x]=A[i]
            
    print(len(lbds))
    
if __name__=="__main__":
    main()


### FIXED CODE ###

# ABC134E

import sys
input=sys.stdin.readline

def bisectR(ite,x):
    st=-1
    en=len(ite)
    while(en-st>1):
        mid=(en+st)//2
        if ite[mid]<x:
            en=mid
        else:
            st=mid
    return en

def main():
    N=int(input())
    A=[int(input()) for i in range(N)]
    
    lbds=[A[0]]
    for i in range(1,N):
        if lbds[-1]>=A[i]:
            lbds+=[A[i]]
        else:
            x=bisectR(lbds,A[i])
            lbds[x]=A[i]
    print(len(lbds))
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]
 
N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L2 = sorted(L1)
ans = 0
for i in range(N):
    if L2[i][1] > 0:
        ans += L2[i][1]
        lim = L2[i][0] + 2*D
        for j in range(1,N-i):
            if L2[i+j][0] <= lim:
                L2[i+j][1] -= L2[i][1]
            else:
                break
        L2[i][1] -= L2[i][1]
print(ans)

### FIXED CODE ###

import sys,math
sr = sys.stdin.readline
def I(i=0):return [int(x)-i for x in sr().split()]
L1,L2 = [],[]

N,D,A = I()
for i in range(N):
    X,H = I()
    L1.append([X,math.ceil(H/A)])
L1 = sorted(L1)
j = 1
L2 = [-1]*N
for i in range(N):
    lim = L1[i][0] + 2*D
    for k in range(j,N):
        if L1[k][0] > lim:
            L2[i] = k-1
            j = k-1
            break
        elif k == N-1:
            L2[i] = N-1
            j = N-1
ans = 0
a,s = 0,0
for i in range(N):
    x,h = L1[i]
    h -= a
    if h > 0:
        ans += h
        a += h
        L1[i][1] = h
    else:
        L1[i][1] = 0
    while s < N and L2[s] <= i:
        a -= L1[s][1]
        s += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [[]]
for i in range(N):
    A.append(LIST()[::-1])

cnt = N*(N-1)//2
nxtli = set(range(1, N+1))
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    # 前回変更があった場所のみでループを回す
    curli = nxtli.copy()
    nxtli = set()
    for i in curli:
        if len(A[i]) and not skip[i]:
            a = A[i][-1]
            if len(A[a]) and not skip[a]:
                b = A[a][-1]
                if i == b:
                    A[i].pop()
                    A[a].pop()
                    # 変更があった場所をセットに入れておく
                    if len(A[i]):
                        nxtli.add(i)
                    if len(A[a]):
                        nxtli.add(a)
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1
print(day)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

start = time.time()

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)
### BUGGY CODE ###

from pprint import pprint

n,w = map(int,input().split())

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(n+1) for _ in range(w+1)]

dp_table[0][0] = 0

for i in range(1,n+1):
    for before_w in range(w):
        #i番目の品物を選ばない場合
        dp_table[before_w][i] = max(dp_table[before_w][i], dp_table[before_w][i-1])
        #i番目の品物を選ぶ場合
        if wv[i-1][0]+before_w <= w:
            dp_table[wv[i-1][0]+before_w][i] = max(dp_table[wv[i-1][0]+before_w][i], dp_table[before_w][i-1] + wv[i-1][1])
        else:
            continue

result_list=[]

for y in range(w+1):
    result_list.append(max(dp_table[y]))

print(max(result_list))

### FIXED CODE ###

from pprint import pprint

n,w = map(int,input().split())

wv = [list(map(int,input().split())) for _ in range(n)]


dp_table = [[-float("inf")]*(w+1) for _ in range(n+1)]

dp_table[0] = [0]*(w+1)

#sum_w以下の重さの時のvalueの合計の最大を求めていく。

for i in range(1,n+1):
    for sum_w in range(w+1):
        #i番目の品物を選ばない場合
        dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w])
        #i番目の品物を選ぶ場合
        if sum_w >= wv[i-1][0]:
            dp_table[i][sum_w] = max(dp_table[i][sum_w], dp_table[i-1][sum_w-wv[i-1][0]] + wv[i-1][1])
        else:
            continue


result = dp_table[n][w]
print(result)
### BUGGY CODE ###

def main():

    s = input()
    q = int(input())

    query = [input().split() for _ in range(q)]
    ctn = query.count(["1"])

    flag = 0
    for q in query:
        if q[0] == "1":
            if flag == 1:
                flag = 0
            else:
                flag = 1
        else:
            if flag == 0:
                if q[1] == "1":
                    s = q[2] + s
                else:
                    s = s + q[2]
            else:
                if q[1] == "1":
                    s = s + q[2]
                else:
                    s = q[2] + s

    if ctn % 2 == 1:
        print(s[::-1])
    else:
        print(s)

main()


### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

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

ans = 1

for i in range(N):
  if 0 in A:
    ans = 0
    break
  ans *= A[i]
  i += 1
  if ans > 10**18:
    ans = -1
    break

print(ans)

### FIXED CODE ###

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

ans = 1

if 0 in A:
  ans = 0
else:
  for i in range(N):
    ans *= A[i]
    i += 1
    if ans > 10**18:
      ans = -1
      break

print(ans)