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

s=list(input())
q=int(input())
sc=0
for _ in range(q):
  query=input()
  if query=="1":
    sc+=1
  else:
    t,f,c=query.split()
    if f=="1":
      if sc%2==0:
        s=[c]+s
      else:
        s=s+[c]
    else:
      if sc%2==0:
        s=s+[c]
      else:
        s=[c]+s
if sc%2!=0:
  s.reverse()
print("".join(s))

### FIXED CODE ###

s=list(input())
q=int(input())
sc=0
lhs=[]
rhs=[]
for _ in range(q):
  query=input()
  if query=="1":
    sc+=1
  else:
    t,f,c=query.split()
    if f=="1":
      if sc%2==0:
        lhs.append(c)
      else:
        rhs.append(c)
    else:
      if sc%2==0:
        rhs.append(c)
      else:
        lhs.append(c)

lhs.reverse()
s=lhs+s+rhs
if sc%2!=0:
  s.reverse()
print("".join(s))
### BUGGY CODE ###

K = int(input())

def computeGCD(x, y):
    while (y):
        x, y = y, x % y

    return x

sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sum += computeGCD(a, computeGCD(b, c))

print(sum)

### FIXED CODE ###

import math
K = int(input())

def computeGCD(x, y):
    while (y):
        x, y = y, x % y

    return x

sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        intermediate = computeGCD(a, b)
        for c in range(1, K+1):
            sum += computeGCD(c, intermediate)

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

MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
def main():
    S = input()
    l = len(S)
    dp = [[0]*(13) for _ in range(len(S)+5)]
    dp[0][0] = 1
    mul = 1  
    for i in range(l):
        x = S[-(i+1)]
        if x == "?":
            for k in range(10):
                for j in range(13):
                    dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                    dp[i + 1][(mul * k + j) % 13] %= MOD
        else:
            k = int(x) # これしか選ぶ余地なし
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
        mul *= 10 % 13
    print(dp[l][5]%MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
  print(a.index(i)+1, end=" ")

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))

turn=[" " for _ in range(n)]
for i in range(n):
  turn[a[i]-1]=i+1

for i in range(n):
  print(turn[i], end=" ")
### BUGGY CODE ###

ans=0
n=int(input())
a=[int(input()) for _ in range(n)]
b=list(set(a))
for i in b:
    if a.count(i)%2==0:
        continue
    else:
        ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(input()) for i in range(n)]

c=Counter(a)
ans=0
for i in c.values():
    if i%2!=0:
        ans+=1

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

import collections
import numpy as np

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

ca = collections.Counter(A)
cakeys = list(ca.keys())
cavalues = np.array(list(ca.values()))

#print(cakeys)
#print(np.array(list(ca.values())))

cavaluesmax = cavalues*(cavalues-1)//2
cavaluesmin = (cavalues-1)*(cavalues-2)//2

#print(cavaluesmax)
#print(cavaluesmin)

ans = 0
for i in range(N):
    #print(cakeys[index])
    index = cakeys.index(A[i])
    ans = cavaluesmin[index].sum() + cavaluesmax[:index].sum() + cavaluesmax[index+1:].sum()
    print(ans)


### FIXED CODE ###

import collections
from collections import deque
import numpy as np

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

ca = collections.Counter(A)
cakeys = list(ca.keys())
cavalues = np.array(list(ca.values()))

#print(cakeys)
#print(np.array(list(ca.values())))

cavaluesmax = cavalues*(cavalues-1)//2
valuesum = np.sum(cavaluesmax)
#cavaluesmin = (cavalues-1)*(cavalues-2)//2


for a in A:
    #print(cakeys[index])
    v = ca[a]
    ans = valuesum - v + 1
    #ans = cavaluesmin[index].sum() + cavaluesmax[:index].sum() + cavaluesmax[index+1:].sum()
    print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]

hdots = [[0]*(w+1) for _ in range(h)]
for j in range(h):
    ndots = 0
    for i in range(1, w+1):
        if s[j][i-1] == '.':
            ndots += 1
        else:
            hdots[j][i-1] = ndots
            ndots = 0
    hdots[j][-1] = ndots if s[j][-1] == '.' else 0
    for i in range(w, 0, -1):
        if s[j][i-1] == '.':
            hdots[j][i] = ndots
        else:
            ndots = hdots[j][i-1]
vdots = [[0]*w for _ in range(h+1)]
for i in range(w):
    ndots = 0
    for j in range(1, h+1):
        if s[j-1][i] == '.':
            ndots += 1
        else:
            vdots[j-1][i] = ndots
            ndots = 0
    vdots[-1][i] = ndots if s[-1][i] == '.' else 0
    for j in range(h, 0, -1):
        if s[j-1][i] == '.':
            vdots[j][i] = ndots
        else:
            ndots = vdots[j-1][i]

ans = 0
for j in range(h):
    for i in range(w):
        nh, nv = hdots[j][i+1], vdots[j+1][i]
        if nh == 0 or nv == 0:
            continue
        ans = max(ans, nh+nv-1)
print(ans)


### FIXED CODE ###

# Refered #5850116 submit
import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)]) == '.'

ups = np.zeros((h, w), dtype = int)
downs = np.zeros((h, w), dtype = int)
lefts = np.zeros((h, w), dtype = int)
rights = np.zeros((h, w), dtype = int)

for i in range(1, h):
    ups[i] = (ups[i-1]+1)*s[i-1]
for i in range(h-2, -1, -1):
    downs[i] = (downs[i+1]+1)*s[i+1]
for j in range(1, w):
    lefts[:, j] = (lefts[:, j-1]+1)*s[:, j-1]
for j in range(w-2, -1, -1):
    rights[:, j] = (rights[:, j+1]+1)*s[:, j+1]
counts = ups+downs+lefts+rights
ans = np.max(counts*s)+1
print(ans)
### BUGGY CODE ###

from math import gcd

A, B = map(int, input().split())

m = gcd(A, B)
#print(m)

num = m+1
ans = 1

for i in range(2,num):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m = m/i

print(ans)

### FIXED CODE ###

from math import gcd

A, B = map(int, input().split())

m = gcd(A, B)
#print(m)

num = int(m**0.5) #mに対する素因数分解は、int(√m)の場合を調べればよい
ans = 1

for i in range(2,num+1):
    if m%i:
        continue
    ans += 1
    while not m%i:
        m /= i

if m>1:
    ans+=1 #m+1が素因数の場合がある

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

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 B
"""

import itertools

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

cut = 10**9+7


def modInverse(a, b, divmod=divmod):
    r0, r1, s0, s1 = a, b, 1, 0
    while r1 != 0:
        q, rtmp = divmod(r0, r1)
        stmp = s0-q*s1
        r0, s0 = r1, s1
        r1, s1 = rtmp, stmp
    return s0 % cut


def factorial(n):
    nn = 1
    for i in range(2, n+1):
        nn = nn*i
    return(nn)


invlist = [modInverse(i, cut) for i in range(1, n+1)]
accuminv = list(itertools.accumulate(invlist, func=lambda x, y: x+y % cut))

ans = 0
nfact = factorial(n)
for i in range(n):
    sump = accuminv[i]+accuminv[n-1-i] - 1
    ans += ali[i]*sump % cut

ans = ans*nfact % cut
print(ans)




### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 B
"""

import itertools
import math

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

cut = 10**9+7


def modInverse(a, b, divmod=divmod):
    r0, r1, s0, s1 = a, b, 1, 0
    while r1 != 0:
        q, rtmp = divmod(r0, r1)
        stmp = s0-q*s1
        r0, s0 = r1, s1
        r1, s1 = rtmp, stmp
    return s0 % cut


# def factorial(n):
#     nn = 1
#     for i in range(2, n+1):
#         nn = nn*i
#     return(nn)


invlist = [modInverse(i, cut) for i in range(1, n+1)]
accuminv = list(itertools.accumulate(invlist, func=lambda x, y: x+y % cut))

ans = 0
nfact = math.factorial(n)
for i in range(n):
    sump = accuminv[i]+accuminv[n-1-i] - 1
    ans += ali[i]*sump % cut

ans = ans*nfact % cut
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
sys.setrecursionlimit(1000000)
 
H,W = map(int,input().split())
S = [input() for i in range(H)]

L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W+1)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            L[i][j] = L[i][j-1] + 1
        else:
            L[i][j] = 0
            
        if S[i][W-1-j] == ".":
            R[i][W-1-j] = R[i][W-1-j+1] + 1
        else:
            R[i][W-1-j] = 0
        
U = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H+1)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            U[i][j] = U[i-1][j] + 1
        else:
            U[i][j] = 0
           
        if S[H-1-i][j] == ".":
            D[H-1-i][j] = D[H-1-i+1][j] + 1
        else:
            D[H-1-i][j] = 0
        
        
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
            
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
 
H,W = map(int,input().split())
S = [input() for i in range(H)]

L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W+1)] for j in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            L[i][j] = L[i][j-1] + 1
        else:
            L[i][j] = 0
            
        if S[i][W-1-j] == ".":
            R[i][W-1-j] = R[i][W-1-j+1] + 1
        else:
            R[i][W-1-j] = 0
        
U = [[0 for i in range(W)] for j in range(H)]
D = [[0 for i in range(W)] for j in range(H+1)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            U[i][j] = U[i-1][j] + 1
        else:
            U[i][j] = 0
           
        if S[H-1-i][j] == ".":
            D[H-1-i][j] = D[H-1-i+1][j] + 1
        else:
            D[H-1-i][j] = 0
        
        
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
            
print(ans)
### BUGGY CODE ###

from collections import deque
S=input()
d=deque(S)
rev=False
Q=int(input())
for i in range(Q):
    Que=input()
    if(Que=='1'):
        rev=True if not rev else False
    else:
        T,F,C=map(str,Que.split())
        if(F=='1'):
            if(not rev):
                d.appendleft(C)
            else:
                d.append(C)
        elif(F=='2'):
            if(not rev):
                d.append(C)
            else:
                d.appendleft(C)
if(not rev):
    for i in range(len(d)):
        print(d[i],end='')
else:
    for i in reversed(range(len(d))):
        print(d[i],end='')


### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
V = [v for w, v in wv]
INF = 10**10
v_max = sum(V)
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if dp[i+1][j] <= W and j > ans:
            ans = j
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
wv = []
for _ in range(N):
    wv.append(list(map(int, input().split())))
INF = 10**10
v_max = 10**5
dp = [[INF]*(v_max+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for i in range(N):
    for j in range(v_max+1):
        if j >= wv[i][1]:
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]]+wv[i][0])
            #print(i, j, dp[i+1][j], dp[i][j], wv[i][0])
        else:
            dp[i+1][j] = dp[i][j]
        if i+1 == N and dp[i+1][j] <= W:
            ans = j
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]
T = [int(input()) for i in range(D)]
M = int(input())
DQ = [tuple(map(int,input().split())) for i in range(M)]

score = 0
lasts = [[0] for i in range(26)]
for i,(s,a) in enumerate(zip(S,T)):
    score += s[a-1]
    lasts[a-1].append(i+1)
for j in range(26):
    lasts[j].append(D+1)

for j,(c,ls) in enumerate(zip(C,lasts)):
    for a,b in zip(ls,ls[1:]):
        score -= c * (b-a)*(b-a-1)//2

from bisect import insort
for d,q in DQ:
    p = T[d-1]
    T[d-1] = q
    score += (S[d-1][q-1] - S[d-1][p-1])
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score += C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score += C[q-1] * (b-a)*(b-a-1)//2
    i = lasts[p-1].index(d)
    del lasts[p-1][i]
    insort(lasts[q-1], d)
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score -= C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score -= C[q-1] * (b-a)*(b-a-1)//2
    print(score)

### FIXED CODE ###

import sys
input = sys.stdin.readline
D = int(input())
C = list(map(int,input().split()))
S = [list(map(int,input().split())) for i in range(D)]
T = [int(input()) for i in range(D)]
M = int(input())
DQ = [tuple(map(int,input().split())) for i in range(M)]

score = 0
lasts = [[0] for i in range(26)]
for i,(s,a) in enumerate(zip(S,T)):
    score += s[a-1]
    lasts[a-1].append(i+1)
for j in range(26):
    lasts[j].append(D+1)

for j,(c,ls) in enumerate(zip(C,lasts)):
    for a,b in zip(ls,ls[1:]):
        score -= c * (b-a)*(b-a-1)//2

from bisect import bisect
for d,q in DQ:
    p = T[d-1]
    T[d-1] = q
    score += (S[d-1][q-1] - S[d-1][p-1])
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score += C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score += C[q-1] * (b-a)*(b-a-1)//2
    i = lasts[p-1].index(d)
    del lasts[p-1][i]
    i = bisect(lasts[q-1], d)
    lasts[q-1].insert(i,d)
    for a,b in zip(lasts[p-1],lasts[p-1][1:]):
        score -= C[p-1] * (b-a)*(b-a-1)//2
    for a,b in zip(lasts[q-1],lasts[q-1][1:]):
        score -= C[q-1] * (b-a)*(b-a-1)//2
    print(score)
### BUGGY CODE ###

N, K = map(int, input().split())
res = [N]
if N % K == 0:
  print(0)
else:
  while True:
    M = abs(N - K)
    if M  in res:
      break
    elif M not in res:
      N = M
      res.append(N)
  print(min(res))

### FIXED CODE ###

N, K = map(int, input().split())
cand1 = N % K
cand2 = K - (N % K)
print(min(cand1, cand2))
### BUGGY CODE ###

def knapsack(W,n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max( val[n-1] + knapsack(W-wt[n-1], n-1),  knapsack(W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack( W, n-1) 
        return t[n][W] 
  

    
wt,val=[],[]
n,w=map(int,input().split())
t=[[-1 for i in range(w+1)]for j in range(n+1)]
for _ in range(n):
    temp_wt,temp_pr=map(int,input().split())
    wt.append(temp_wt)
    val.append(temp_pr)
print(knapsack(w,n))




### FIXED CODE ###

n,W=map(int,input().split())
t = [[-1 for i in range(W + 1)] for j in range(n + 1)] 
  
  
def knapsack(wt, val, W, n):     
  
    # base conditions 
    if n == 0 or W == 0: 
        return 0
    if t[n][W] != -1: 
        return t[n][W] 
  
    # choice diagram code 
    if wt[n-1] <= W: 
        t[n][W] = max(val[n-1] + knapsack(wt, val, W-wt[n-1], n-1),knapsack(wt, val, W, n-1)) 
        return t[n][W] 
    elif wt[n-1] > W: 
        t[n][W] = knapsack(wt, val, W, n-1) 
        return t[n][W] 

weight,profit=[],[]
for _ in range(n):
  w,p=map(int,input().split())
  weight.append(w)
  profit.append(p) 
print(knapsack(weight,profit, W, n))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

# modを取りながらべき乗する
def power_func(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

def main():
    N, C = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    mod = 10**9+7

    dp = [[[] for _ in range(C+1)] for _ in range(N)]
    count = B[0] - A[0] + 1
    for c in range(C+1):
        a, b = A[0], B[0]
        dp[0][c].append(power_func(a, c, mod))
        for k in range(1, b-a+1):
            dp[0][c].append((dp[0][c][k-1] + power_func(a+k, c, mod)) % mod)

    for i in range(1, N):
        a, b = A[i], B[i]
        for k in range(b-a+1):
            dp[i][0].append(count * (k+1) % mod)
        for c in range(1, C+1):
            dp[i][c].append((dp[i-1][c][-1] + a*dp[i][c-1][0]) % mod)
            for k in range(1, b-a+1):
                R = dp[i][c][k-1] + dp[i-1][c][-1] + (a+k)*(dp[i][c-1][k]-dp[i][c-1][k-1])
                if R < 0: R += mod
                dp[i][c].append(R%mod)
        count = (count * (b-a+1)) % mod

    print(dp[N-1][C][-1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

# modを取りながらべき乗する
def power_func(a,n,mod):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

def main():
    N, C = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    mod = 10**9+7
    L = 400

    dp = [[0]*(L+1) for _ in range(C+1)]
    count = B[0] - A[0] + 1
    for c in range(C+1):
        a, b = A[0], B[0]
        dp[c][0] = power_func(a, c, mod)
        for k in range(1, b-a+1):
            dp[c][k] = (dp[c][k-1] + power_func(a+k, c, mod)) % mod
        dp[c][L] = dp[c][b-a]

    for i, (a, b) in enumerate(zip(A, B)):
        if i == 0: continue
        for k in range(b-a+1):
            dp[0][k] = count * (k+1) % mod
        dp[0][L] = dp[0][b-a]
        for c in range(1, C+1):
            dp[c][0] = (dp[c][L] + a*dp[c-1][0]) % mod
            for k in range(1, b-a+1):
                R = dp[c][k-1] + dp[c][L] + (a+k)*(dp[c-1][k]-dp[c-1][k-1])
                if R < 0: R += mod
                dp[c][k] = R%mod
            dp[c][L] = dp[c][b-a]
        count = (count * (b-a+1)) % mod

    print(dp[C][L])


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

n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))
mod = 1000000007

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


for i in range(1, n+1):
    memo[i] = memo[i-1] + memo[i-2]
    if i in a:
        memo[i] = 0

print(memo[-1]%mod)

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))

mod = 1000000007

memo = [-1]*(n+1)
memo[0] = 0

for k in range(m):
    memo[a[k]] = 0

for i in range(1, n+1):
    if memo[i] != -1:
        pass 
    elif i <= 2:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[-1]%mod)
### BUGGY CODE ###

from pprint import pprint
import numpy as np
n,w=map(int, input().split())
wl,vl=[],[]
wsum=0
for i in range(n):
  wn,v=map(int, input().split())
  wl.append(wn)
  vl.append(v)
  wsum+=w
if wsum<w:
  w=wsum

dp=[[0]*(w+1) for i in range(n+1)]
wmin=min(wl)

for wsum in range(wmin,w+1):
  #print("重さ：{}".format(wsum))
  for i in range(n):
    #print("i={}".format(i))
    if wsum >= wl[i]:
        #print("選ぶ, (重さ：{}, 価値：{})".format(wl[i], vl[i]))
        dp[i+1][wsum] = max(dp[i+1][wsum], dp[i][wsum-wl[i]]+vl[i])
    else:
      dp[i+1][wsum] = dp[i][wsum]
    #pprint(dp)
dp=np.array(dp)
print(np.max(dp))


### FIXED CODE ###

from pprint import pprint
import numpy as np
import numba as nb
@nb.njit
def Knapsack1(n,w,wl,vl):
  dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
  for wsum in range(1,w+1):
  	#print("i={}".format(i))    
    for i in range(n):
      #print("重さ：{}".format(wsum))
      if wsum >= wl[i]:
        if dp[i][wsum] < dp[i][wsum-wl[i]]+vl[i]:
          #print("選ぶ, (重さ：{}, 価値：{})".format(wv[i][0], wv[i][1]))
          dp[i+1][wsum] = dp[i][wsum-wl[i]]+vl[i]
        else:
          dp[i+1][wsum] = dp[i][wsum]
          
      else:
        dp[i+1][wsum] = dp[i][wsum]
  #print(dp)
  print(dp[-1][-1])

n,w=map(int, input().split())
wv=[list(map(int,input().split()))  for i in  range(n)]
wv.sort(key=lambda x:(x[1],x[0]))
wv=np.array(wv)
wv=wv.T
wl=wv[0]
vl=wv[1]
#print(wl)
#print(vl)
Knapsack1(n,w,wl,vl)
### BUGGY CODE ###

N = int(input())

S = []
for i in range(N):
    S.append("".join(sorted(list(input()))))

cnt = 0
for i in range(N):
    cnt += S[i+1:].count(S[i])
    
print(cnt)

### FIXED CODE ###

N = int(input())

S = []
cnt = 0
c = {}

for i in range(N):
    s = "".join(sorted(list(input())))
    if s not in c.keys():
        c[s] = 1
    else:
        c[s] += 1
        cnt += c[s]-1
        
    S.append(s)

print(cnt)
### BUGGY CODE ###

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

for i in range(q):
    t_f_c = list(input().split())
    if t_f_c[0] == "1":
        s = list(s)
        s.reverse()
        s = "".join(s)
    elif t_f_c[0] == "2":
        if t_f_c[1] == "1":
            s = t_f_c[2] + s
        elif t_f_c[1] == "2":
            s = s + t_f_c[2]
print(s)


### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())

cnt = 1
for i in range(q):
    t_f_c = list(input().split())
    if t_f_c[0] == "1":
        cnt *= -1
    elif t_f_c[0] == "2":
        if cnt == 1: #反転-
            if t_f_c[1] == "1":
                s.appendleft(t_f_c[2])
            elif t_f_c[1] == "2":
                s.append(t_f_c[2])
        elif cnt == -1:  #反転+
             if t_f_c[1] == "2":
                s.appendleft(t_f_c[2])
             elif t_f_c[1] == "1":
                s.append(t_f_c[2])
if cnt == 1:
    print("".join(s))
elif cnt == -1:
    s.reverse()
    print("".join(s))
### BUGGY CODE ###

from collections import deque
a = list(input())
Q = int(input())
B = []
C = []
A = [list(input().split()) for _ in range(Q)]
d = deque(a)
for i in range(len(A)):
  if len(A[i]) == 1:
    d.reverse()
  elif A[i][1] == "1":
    d.appendleft(A[i][2])
  elif A[i][1] == "2":
    d.append(A[i][2])
print(''.join(d))

### FIXED CODE ###

from collections import deque
a = list(input())
Q = int(input())
d = deque(a)
ans = 1
for i in range(Q):
  b = list(input().split())
  if len(b) == 1:
    ans += 1
  elif b[1] == "1" and ans % 2 == 1:
    d.appendleft(b[2])
  elif b[1] == "1" and ans % 2 == 0:
    d.append(b[2])
  elif b[1] == "2" and ans % 2 == 1:
    d.append(b[2])
  elif b[1] == "2" and ans % 2 == 0:
    d.appendleft(b[2])
if ans % 2 == 0:
  d.reverse()
print("".join(d))