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

N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,l+1):       
        for j in range(1,l+1):
            if i*i + j*j + i*j > l:
                break;
            for k in range(1,l+1):
                #print(i,j,k,l)
                if i*i + j*j + k*k + i*j +j*k + i*k > l:
                    break;
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

### FIXED CODE ###

N = int(input())
list = [0]*(N+1)
for i in range(1,100):  
    for j in range(1,100):
        a = i*i + j*j + i*j
        for k in range(1,100):
            a = i*i + j*j + k*k + i*j +j*k + i*k
            if a <= N:
                list[a] += 1
for i in range(1,N+1):
    print(list[i])
### BUGGY CODE ###

import math

def siki(A, B, X):
	return math.floor((A*X)/B) - A*math.floor(X/B)

A,B,N = map(int,input().split())
x = N
max_value = 0

if B > A * N:
	print(0)
else:
	if N < B:
		k = N
	else:
		k = B
	for i in range(1, k+1):
		if max_value < siki(A,B,i):
			max_value = siki(A,B,i)

	print(max_value)


### FIXED CODE ###

import math

def f(A, B, X):
	return math.floor((A*X)/B) - A*math.floor(X/B)

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

if N < B:
	print(f(A,B,N))
else:
	print(f(A,B,B-1))
### BUGGY CODE ###

K, S = map(int, input().split())

# a = []
ans = 0
for i in range(K + 1):
    for j in range(i + 1):
        for k in range(j + 1):
            # print(i, j, k)
            if i + j + k == S:
                # print(i, j, k)
                # tmp = [i, j, k]
                # a.append(tmp)
                if i == j and j == k:
                    ans += 1
                elif i == j or j == k:
                    ans += 3
                else:
                    ans += 6

print(ans)


### FIXED CODE ###

K, S = map(int, input().split())

# a = []
ans = 0
for i in range(K + 1):
    for j in range(i + 1):
        k = S - i - j
        if k >= 0 and k <= j:
            # print(i, j, k)
            if i == j and j == k:
                ans += 1
            elif i == j or j == k:
                ans += 3
            else:
                ans += 6

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

import copy


def score(list):
    tl, dl = zip(*list)
    t_s = len(set(tl)) ** 2
    d_s = sum(dl)
    return t_s + d_s


def r(n, k, sl):

    for _ in range(len(sl) - k):

        ckl = {}
        for v in sl:
            if v[0] in ckl:
                if ckl[v[0]][1] > v[1]:
                    ckl[v[0]] = v
            else:
                ckl[v[0]] = v

        s_c = 0
        dtl = []
        for delckl in ckl.values():
            c_sl = copy.copy(sl)
            del c_sl[c_sl.index(delckl)]
            soe = score(c_sl)
            if s_c < soe:
                s_c = soe
                dtl = delckl

        del sl[sl.index(dtl)]

    return score(sl)


def main():
    n, k = list(map(int, input().split()))
    sl = [list(map(int, input().split())) for i in range(n)]
    print(r(n, k, sl))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def r(n, k, sl):

    sl.sort(key=lambda x: -x[1])

    gmk = set()
    gop = 0
    ce = []
    for ti, di in sl[:k]:
        if ti in gmk:
            ce.append(di)
        gmk.add(ti)
        gop += di

    gscr = len(gmk)**2 + gop

    for ti, di in sl[k:]:
        if 0 >= len(ce):
            break
        if ti in gmk:
            continue
        gmk.add(ti)
        odi = ce.pop()
        gop = gop - odi + di
        nscr = len(gmk)**2 + gop
        gscr = max(gscr, nscr)

    return gscr


def main():
    input = sys.stdin.readline
    n, k = list(map(int, input().split()))
    sl = [tuple(map(int, input().split())) for _ in range(n)]
    print(r(n, k, sl))


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

n = int(input())
p = list(map(int,input().split()))
ans = 0
for i in range(n):
    if all(p[i] <= p[j] for j in range(i)):
        ans += 1
print(ans)


### FIXED CODE ###

import math
import copy

neko = 0
low = 10**6
n = int(input())
p = [int(x) for x in input().split()]
for i in range(n):
    if p[i]<low:
        neko += 1
    if p[i]<low:
        low = p[i]
print(neko)
### BUGGY CODE ###

#coding:utf-8
N = int(input())
A = list(map(int,input().split()))
sm = 0
MOD = 1000000007
for i in range(len(A)-1):
    for j in range(i+1,len(A)):
        sm += A[i]^A[j]
        sm = sm % MOD
print (sm)

# print (MOD)
# left = [0]
# for a in A:
#     sm+=a
#     sm = sm % MOD
#     left.append(sm)
# print (left)
# sm = 0
# right = [0]
# for a in A[::-1]:
#     sm+=a
#     sm = sm % MOD
#     right.append(sm)
# right = right[::-1]
# print (right)


# ans = 0
# for i in range(len(A)):
#     sm = left[i]+right[i+1]
#     if (len(A)%2==0):
#         sm = sm^A[i]
#     ans += sm
#     ans = ans % MOD
# print (ans)

### FIXED CODE ###

#coding:utf-8
MOD = 10 ** 9 + 7
n = int(input())
A = list(map(int, input().split()))
ans = 0
b = 1
for _ in range(60):
    sm = sum(a&b for a in A)
    sm //= b
    ans = (ans + sm * (n-sm) * b) % MOD
    b<<=1
print (ans)
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = 0
for i in range(n-1):
    j = 0
    count=0
    while h[i+j]>=h[i+j+1]:
        count+=1
        ans=max(ans,count)
        j+=1
        if i+j+1>=n:
            break
print(ans)


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = 0
count=0
for i in range(n-1):
    if h[i]>=h[i+1]:
        count+=1
        ans=max(ans,count)
    else:
        count=0
print(ans)
### BUGGY CODE ###

import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    while c <= N:
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B

print(ans)


### FIXED CODE ###

import sys
import math

sys.setrecursionlimit(10 ** 7)

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

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

ans = 0

if N < B - 1:
    ans = math.floor(A * N / B) - A * math.floor(N / B)
else:
    c = B - 1
    cnt = 1
    while c <= N:
        cnt += 1
        t = math.floor(A * c / B) - A * math.floor(c / B)
        ans = max(ans, t)
        c += B
        if B < cnt:
            break

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

def check(a,b):
    if a==b:
        a=-1

A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
A3=list(map(int,input().split()))
N=int(input())
B=list(map(int,input().split()))

i = 0
j = 0
while i<N:
    while j<3:
        check(A1[j],B[i])
while i<N:
    while j<3:
        check(A2[j],B[i])
while i<N:
    while j<3:
        check(A3[j],B[i])

if A1[0]==A1[1]==A1[2] or A2[0]==A2[1]==A2[2] or A3[0]==A3[1]==A3[2] or A1[0]==A2[0]==A3[0] or A1[1]==A2[1]==A3[1] or A1[2]==A2[2]==A3[2] or A1[0]==A2[1]==A3[2] or A1[2]==A2[1]==A3[0]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
A3=list(map(int,input().split()))
N=int(input())

i = 0
for i in range(N):
    b = int(input())
    j = 0
    while j<3:
        if A1[j]==b:
            A1[j]=-1
        j+=1
    j = 0
    while j<3:
        if A2[j]==b:
            A2[j]=-1
        j+=1
    j = 0
    while j<3:
        if A3[j]==b:
            A3[j]=-1
        j+=1


if A1[0]==A1[1]==A1[2] or A2[0]==A2[1]==A2[2] or A3[0]==A3[1]==A3[2] or A1[0]==A2[0]==A3[0] or A1[1]==A2[1]==A3[1] or A1[2]==A2[2]==A3[2] or A1[0]==A2[1]==A3[2] or A1[2]==A2[1]==A3[0]:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)
S = sum(A)

D = dict()


def f(i, r, g, b):
    if (i, r, g, b) in D.keys():
        return D[(i, r, g, b)]

    if max([r, g, b]) * 2 >= S:
        D[(i, r, g, b)] = 0
        return 0

    if i == N:
        D[(i, r, g, b)] = 1
        return 1

    D[(i, r, g, b)] = 0
    D[(i, r, g, b)] += f(i+1, r+A[i], g, b)
    D[(i, r, g, b)] += f(i+1, r, g+A[i], b)
    D[(i, r, g, b)] += f(i+1, r, g, b+A[i])

    return D[(i, r, g, b)] % 998244353

print(f(0, 0, 0, 0))


### FIXED CODE ###

mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)

PS = [0 for i in range(N+1)]
for i in range(N):
    PS[i+1] = PS[i] + A[i]

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] = (D[i+1][j] + D[i][j] * 2) % mod
        D[i+1][j+A[i]] = (D[i+1][j+A[i]] + D[i][j]) % mod

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] = (D2[i+1][j] + D2[i][j]) % mod
        D2[i+1][j+A[i]] = (D2[i+1][j+A[i]] + D2[i][j]) % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)
### BUGGY CODE ###

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,K+1):
    for j in range(2**i):
        gem = []
        flag = True
        A = 0
        B = -1
        for k in range(i):
            if (j >> k) & 1 == 1:
                if A <= N-1:
                    gem.append(V[A])
                    A += 1
                else:
                    flag = False
                    break
            else:
                if B >= -N:
                    gem.append(V[B])
                    B -= 1
                else:
                    flag = False
                    break
        if flag:
            gem.sort(reverse = True)
            for l in range(K-i):
                if gem and gem[-1] < 0:
                    gem.pop()
            ans.append(sum(gem))
print(max(ans))
        

### FIXED CODE ###

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,min(K,N)+1):
    for a in range(i+1):
        b = i-a
        AB = V[:a]
        if b > 0:
            AB += V[-b:]
        AB.sort(reverse = True)
        for j in range(K-i):
            if AB and AB[-1] < 0:
                AB.pop()
        ans.append(sum(AB))
print(max(ans))
### BUGGY CODE ###

S =list(input())
L =list(map(int,S))

n = 0
X = 0
while X<1:
	# print(L)
	K = len(L)-1
	# print(K)
	for i in range(K):
		if L[i]+L[i+1]==1:
			L.pop(i)
			L.pop(i)
			n=n+1
			break
		elif i == K-1:
			X=1

# print(L)
print(n*2)

### FIXED CODE ###

S =list(input())
L =list(map(int,S))

print(min(L.count(0),L.count(1))*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

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

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])

from collections import deque
Q=deque()

H=[0]*(N-1)**2

for i in range((N-1)**2):
    if E[i]==[] and len(EREV[i])>0:
        Q.append(i)
        H[i]=1

while Q:
    x=Q.pop()

    for fr in EREV[x]:
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1
            if H[fr]>N*N:
                print(-1)
                sys.exit()
            Q.append(fr)
        

if max(H)==0:
    print(-1)
else:
    print(max(H))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

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

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
            
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1

if min(EDGEIN)<0 or max(EDGEIN)>0:
    print(-1)
else:
    print(max(H))
### BUGGY CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	max_val = 0
	for i in range(N):
		ans += abs(A[i]-(i+1))
		max_val = max(max_val, abs(A[i]-(i+1)))

	for j in range(-max_val, max_val+1):
		this_ans = 0
		for i in range(N):
			this_ans += abs(A[i]-(i+j+1))
		ans = min(ans, this_ans)
	print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N):
		A[i] -= i+1
	A.sort()


	mid1 = A[N//2]
	mid2 = A[N//2]
	if N >= 2:
		mid2 = A[N//2 + 1]

	ans1 = 0
	ans2 = 0
	for i in range(N):
		ans1 += abs(A[i] - mid1)
		ans2 += abs(A[i] - mid2)

	print(min(ans1, ans2))


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

n=int(input())
ans=0
for i in range(1,n+1):
    m=n//i
    m*=i
    for j in range(i,m+1,i):
        ans+=j
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    m=n//i
    m*=i
    for j in range(i,m+1,i):
        ans+=j
print(ans)
### BUGGY CODE ###

import math

def divisorGenerator(n):
    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

if __name__ == '__main__':

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

    gcd_ = math.gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = math.gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = True
        divs = dict()
        for i in A:
            res = list(divisorGenerator(i))
            for el in res:
                if el != 1:
                    if not(el in divs):
                        divs[el] = 0
                    divs[el] += 1
        for value in divs.values():
            if value > 1:
                pairwise = False
                break
        if pairwise:
            print("pairwise coprime")
        else:
            print("setwise coprime")



### FIXED CODE ###

import math


def divisorGenerator(n):

    large_divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n // i)
    for divisor in reversed(large_divisors):
        yield divisor

if __name__ == '__main__':

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

    gcd_ = math.gcd(A[0], A[1])
    for i in range(2, len(A)):
        gcd_ = math.gcd(gcd_, A[i])

    set_wise = False
    if gcd_ == 1:
        set_wise = True
    if not(set_wise):
        print("not coprime")
    else:
        pairwise = True
        divs = dict()
        for i in A:
            res = list(divisorGenerator(i))
            for el in res:
                if el != 1:
                    if not(el in divs):
                        divs[el] = 0
                    divs[el] += 1
                    if divs[el] > 1:
                        print("setwise coprime")
                        exit()
        print("pairwise coprime")
        # for value in divs.values():
        #     if value > 1:
        #         pairwise = False
        #         break
        # if pairwise:
        #     print("pairwise coprime")
        # else:
        #
        #
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in range(n):
    if i == a.index(a_first):
        print(a_second)
    else:
        print(a_first)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_first = sorted(a)[-1]
a_second = sorted(a)[-2]
for i in a:
    print(a_second if i == a_first else a_first)
### BUGGY CODE ###

s = str(input())

s = list(s)

dp = [[0 for _ in range(13)] for __ in range(len(s))] 

if s[0] != "?":
    dp[0][int(s[0])] = 1
else:
    for j in range(10):
        dp[0][j] = 1

for i in range(1,len(s)):
    if s[i] != "?":
        for j in range(13):
            dp[i][(j * 10 + int(s[i])) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i][(j * 10 + k) % 13] += dp[i-1][j]

print(dp[len(s)-1][5] % (10 ** 9 + 7))

### FIXED CODE ###

MOD = 10 ** 9 + 7
 
s = str(input())
 
s = list(s)
 
cur = [0] * 13
 
if s[0] != "?":
    cur[int(s[0])] = 1
else:
    for j in range(10):
        cur[j] = 1
 
for i in range(1,len(s)):
    pre = cur[:]
    cur = [0] * 13
    if s[i] != "?":
        for j in range(13):
            q = (j * 10 + int(s[i])) % 13
            cur[q] += pre[j] % MOD
    else:
        for j in range(13):
            for k in range(10):
                p = (j * 10 + k) % 13
                cur[p] += pre[j] % MOD
 
print(cur[5] % MOD)
### BUGGY CODE ###

import time

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

l = [int(input()) for i in range(N)]

INF = 10 ** 8

stack = []
depth, a, b, c, mp = 0, 0, 0, 0, 0
stack.append([depth, a, b, c, mp])
flg = []

MP = INF

ct = 0
while stack:
    x = stack.pop(-1)
    if x[0] == N:
        a, b, c = x[1], x[2], x[3]
        mp = x[4] + abs(a-A) + abs(b-B) + abs(c-C) - 30
        if min(a, b, c) > 0 and mp < MP:
            MP = mp
    elif x[0] > N:
        pass
    else:
        tmp = tuple(x)
        for i in range(4):
            if i == 0:
                x[0] += 1
            else:
                x[0] += 1
                x[i] += l[x[0]-1]
                x[4] += 10
            if x not in flg:
                stack.append(x)
                flg.append(tuple(x))
            x = list(tmp)
print(MP)


### FIXED CODE ###

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

l = [int(input()) for i in range(N)]


def convert(n):
    list_q = []
    while True:
        a = n % 4
        n //= 4
        list_q.insert(0, a)
        if n == 0:
            break
    list_q = [str(i) for i in list_q]
    return list_q


MP = -1
for i in range(21, 4**N):
    mp_a = 0
    mp_b = 0
    mp_c = 0
    use = [int(j) for j in ''.join(convert(i)).zfill(N)]
    a_n = use.count(1)
    b_n = use.count(2)
    c_n = use.count(3)
    if a_n == 0 or b_n == 0 or c_n == 0:
        pass
    else:
        mp_a += 10 * (a_n - 1)
        mp_b += 10 * (b_n - 1)
        mp_c += 10 * (c_n - 1)
        b_a = 0
        b_b = 0
        b_c = 0
        idx = 0
        for i in use:
            if i == 1:
                b_a += l[idx]
            elif i == 2:
                b_b += l[idx]
            elif i == 3:
                b_c += l[idx]
            idx += 1
        mp_a += abs(A-b_a)
        mp_b += abs(B-b_b)
        mp_c += abs(C-b_c)
        mp = mp_a + mp_b + mp_c
        if MP == -1 or mp < MP:
            MP = mp
print(MP)
### BUGGY CODE ###

import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10

N = 2019
cnt = [0] * N
#print (cnt)

def dec(cnt,s):
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    return new


S = input()
ans = 0
for s in S:
    s = int(s)
    cnt = dec(cnt,s)
    cnt[s] += 1
    ans += cnt[0]
    # if cnt[0] != 0:
    #     print (cnt[0])
print (ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**7)
INF = 10**10

N = 2019
cnt = [0] * N
#print (cnt)

def dec(cnt,s):
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    return new


S = input()[:-1]
ans = 0
for s in S:
    s = int(s)
    cnt = dec(cnt,s)
    cnt[s] += 1
    ans += cnt[0]
    # if cnt[0] != 0:
    #     print (cnt[0])
print (ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 1
for i in range(N):
    ans = ans*L[i]
    if ans <= 10**18 and i == N-1:
        print(ans)
        break
    elif ans >= 10**18 and i == N-1:
        print("-1")
        break


### FIXED CODE ###

import sys
N = int(input())
L = list(map(int,input().split()))
ans = 1

if 0 in L:
    print(0)
    sys.exit()

for i in L:
    ans = ans*i
    if ans > 10**18:
        print(-1)
        sys.exit()
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    Query = input()
    if Query[0] == "1":
        S = S[::-1]
    else:
        QueryList = Query.split()
        if QueryList[1] =="1":
            S = QueryList[2]+S
        else:
            S = S+QueryList[2]

print(S)

### FIXED CODE ###

from collections import deque

d = deque()
S = input()
d.append(S)
Q = int(input())
Flag = True
 
for i in range(Q):
    Query = input()
    if Query[0] == "1":
        Flag = not Flag
    else:
        QueryList = Query.split()
        if Flag:
            if QueryList[1] =="1":
                d.appendleft(QueryList[2])
            else:
                d.append(QueryList[2])
        else:
            if QueryList[1] =="2":
                d.appendleft(QueryList[2])
            else:
                d.append(QueryList[2])

d_string = "".join(list(d))

if not Flag:
    d_string = d_string[::-1]    
print(d_string)
### BUGGY CODE ###

#dp[i]:i+1桁目-n桁目で1桁の数字は/2桁の数字は/何通りあるか
n = int(input())
s = input()+"a"
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            t1 = n-1
            u1 = n-1
            v1 = n-1
            for t in range(n):
                if i == int(s[t]):
                    t1 = t
                    break
            for u in range(t1+1,n):
                if j == int(s[u]):
                    u1 = u
                    break
            for v in range(u1+1,n):
                if k == int(s[v]):
                    v1 = v
                    break
            if int(s[t1]) == i and int(s[u1]) == j and int(s[v1]) == k and t1<u1 and u1<v1:
                #print(i,j,k,t1,u1,v1)
                ans += 1
print(ans) 
            
    

### FIXED CODE ###

#dp[i]:i+1桁目-n桁目で1桁の数字は/2桁の数字は/何通りあるか
n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        t1 = n-1
        u1 = n-1
        for t in range(n):
            if i == int(s[t]):
                t1 = t
                break
        for u in range(t1+1,n):
            if j == int(s[u]):
                u1 = u
                break
        if int(s[t1]) == i and int(s[u1]) == j and t1<u1:
            #print(i,j,k,t1,u1,v1)
            ans += len(set(s[u1+1:]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import io
import os


def main():
    buffer = list(map(int, os.read(0, os.fstat(0).st_size).split()))
    m = buffer[1]
    dp = [0] * (m + 1)
    v1 = buffer[3]
    for i in range(buffer[2], m + 1):
        dp[i] = v1

    for i in range(buffer[0] - 1):
        wi, vi = buffer[4 + 2 * i], buffer[5 + 2 * i]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])


input = io.BytesIO().readline
main()


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

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