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

import itertools
import collections
N,A=map(int,raw_input().split())
#print N,A
x=collections.Counter(map(int,raw_input().split()))
#print x

iv=[i for i in x.keys()]	#Item value
#print "# iv"
#print iv
ic=[]	#Item count
for i in x.items():
	tmp=[i for i in range(i[1]+1)]
	ic.append(tmp)

#print "# ic"
#print ic

ic_n=[len(_)-1 for _ in ic]
#print "# ic_n"
#print ic_n

p=list(itertools.product(*ic))
#print "# p"
#print p		#Pattern

a=[]
for m in p:
	#print "##"
	#print m,iv
	t_sum=0
	for j,k in zip(m,iv):
		t_sum+=j*k
	#print t_sum,len(m)
	if sum(m)!=0 and t_sum/sum(m)==A and t_sum%sum(m)==0 and sum(m)!=0:
		#print m,iv,t_sum,sum(m)
		a.append(m)

#print "# a"
#print a
#print len(a)

ans=0
for i in a:
	#print "=="
	t_cnt=1
	for j,k in zip(i,ic_n):
		if j!=0 or j!=k:
			#print j,k,len(list(itertools.combinations(range(k),j))) 
			t_cnt*=len(list(itertools.combinations(range(k),j)))
	#print t_cnt
	ans+=t_cnt
print ans




### FIXED CODE ###

N,A=map(int,raw_input().split())
x=[0]+map(int,raw_input().split())
#print x
y=map(lambda i:i-A, x)
#print y

max_x=max(max(x),A)
#print max_x

dp=[[0]*(2*N*max_x+1) for i in range(N+1)]

for j in range(N+1):
	for t in range(2*N*max_x):
		if j==0 and t==N*max_x:
			dp[j][t]=1
		elif j>=1 and (t-y[j]<0 or t-y[j]>2*N*max_x):
			dp[j][t]=dp[j-1][t]
		elif j>=1 and t-y[j]>=0 and 2*N*max_x>=t-y[j]: 
			dp[j][t]=dp[j-1][t]+dp[j-1][t-y[j]]
		else:
			dp[j][t]=0

print dp[N][N*max_x]-1
### BUGGY CODE ###

# encoding:utf-8

import copy
import numpy as np
import random

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

h = []
for i in range(n):
    h.append(int(input()))

h.sort()
# print(h)
max_tree = []
min_tree = []
ans = 10**9
for i in range(n-k+1):
    ans = min(max(h[i:i+k])-min(h[i:i+k]),ans)

print(ans)


### FIXED CODE ###

# encoding:utf-8

import copy
import numpy as np
import random

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

h = []
for i in range(n):
    h.append(int(input()))

h.sort()
# print(h)
max_tree = []
min_tree = []
ans = 10**9
for i in range(n-k+1):
    ans = min(h[i+k-1]-h[i],ans)

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

s = input()
n = len(s)
flag = True
while flag:
    n1 = len(s)
    s = s.replace('01', '')
    s = s.replace('10', '')
    n2 = len(s)
    if n1 > n2:
        continue
    else:
        flag = False
        break

print(n-len(s))





### FIXED CODE ###

s = input()

c0 = s.count('0')
c1 = s.count('1')

print(min(c0, c1)*2)
### BUGGY CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.':
            continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0:
            continue

        if xs[i][j+1]>0:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]>0:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        ans=max(ans,x+y-1)

print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

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

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

cnt = 0
while True:
    for i in range(len(A)):
        if A[i] % 2 != 0:
            break
    else:
        A = [a/2 for a in A]
        cnt += 1

print(cnt)


### FIXED CODE ###

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

cnt = 0
while True:
    for i in range(len(A)):
        if A[i] % 2 != 0:
            break
    else:
        A = [a/2 for a in A]
        cnt += 1
        continue
    break

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

n=int(input())
A=list(map(int,input().split()))
divsors=[]
for i in range(n):
  for j in range(1,int(A[i]**(1/2)+1)):
    if A[i]%j==0:
      divsors.append(j)
      if j!=A[i]//j:
        divsors.append(A[i]//j)
set_divsors=sorted(list(set(divsors)))[::-1]
divsors=sorted(divsors)[::-1]
count=[]
for i in range(len(set_divsors)):
  count.append(divsors.count(set_divsors[i]))
for i in range(len(count)):
  if count[i]==n-1 or count[i]==n:
    print(set_divsors[i])
    break

### FIXED CODE ###

n=int(input())
A=[]*n
A[:]=map(int,input().split())

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
      
left=[0]*n
right=[0]*n
for i in range(1,n):
  left[i]=gcd(left[i-1],A[i-1])
  right[n-1-i]=gcd(right[n-i],A[n-i])

ans=0
for i,j in zip(left,right):
  ans=max(ans,gcd(i,j))
print(ans)
### BUGGY CODE ###

s = input()
Q = int(input())
query = [input().split() for _ in range(Q)]

for q in query:
    if q[0] == '1':
        s = s[::-1]
    else:
        if q[1] == '1':
            s = q[2] + s
        else:
            s = s + q[2]
print(s)


### FIXED CODE ###

from collections import deque
s = input()
Q = int(input())
que = deque(s)
cnt = 0
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        cnt += 1
    else:
        reverse = cnt % 2
        if q[1] == '1':
            if reverse == 0:
                s = que.appendleft(q[2])
            else:
                s = que.append(q[2])
        else:
            if reverse == 0:
                s = que.append(q[2])
            else:
                s = que.appendleft(q[2])

ans = ''.join(que)
if cnt % 2 == 0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

S = input()
mod = 10**9+7

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
for i in range(1, len(S)+1):
    s = S[i-1]

    if s == "?":
        for s in range(10):
            for j in range(13):
                dp[i][(10 * j + s) % 13] += dp[i - 1][j]
                dp[i][(10 * j + s) % 13] %= mod
    else:
        s = int(s)
        for j in range(13):
            dp[i][(10*j+s)%13] += dp[i-1][j]
            dp[i][(10*j+s)%13] %= mod
print(dp[len(S)][5])

### FIXED CODE ###

S = input()
mod = 10**9+7

dp = [[0 for j in range(13)] for i in range(len(S)+1)]
dp[0][0] = 1
for i in range(1, len(S)+1):
    s = S[i-1]

    if s == "?":
        for s in range(10):
            for j in range(13):
                dp[i][(10 * j + s) % 13] += dp[i - 1][j]
                dp[i][(10 * j + s) % 13] %= mod
    else:
        s = int(s)
        for j in range(13):
            dp[i][(10*j+s)%13] += dp[i-1][j]
            dp[i][(10*j+s)%13] %= mod
print(dp[len(S)][5])
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        # 4/N - 1/h - 1/n = 1/w
        # (4hn - Nn - Nh) / nhN = 1/w
        # w = nhN / (4hn - Nn - Nh)

        if (4*h*n - N*(n + h)) != 0 and (n*h*N) % (4*h*n - N*(n + h)) == 0:
            w = (n*h*N) // (4*h*n - N*(n + h))
            if w > 0:
                print(h, n, w)
                exit(0)


### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        # 4/N - 1/h - 1/n = 1/w
        # (4hn - Nn - Nh) / nhN = 1/w
        # w = nhN / (4hn - Nn - Nh)

        if (4*h*n - N*(n + h)) > 0 and (n*h*N) % (4*h*n - N*(n + h)) == 0:
            w = (n*h*N) // (4*h*n - N*(n + h))
            print(h, n, w)
            exit(0)
### BUGGY CODE ###

def gcd(x, y):
  while y != 0:
    x, y = y, x%y
  return x

K = int(input())
Klist = [i+1 for i in range(K)]
total = 0
for a in Klist:
  for b in Klist:
    for c in Klist:
      total += gcd(gcd(a, b), c)
print(total)

### FIXED CODE ###

def gcd(x, y):
  while y != 0:
    x, y = y, x%y
  return x
 
K = int(input())
Klist = [i+1 for i in range(K)]
total = 0
for a in Klist:
  for b in Klist:
    for c in Klist:
      total += gcd(gcd(a, b), c)
print(total)
### BUGGY CODE ###

n = int(input())
A = input().split()
a = [int(i) for i in A]
b = [0]*n

for i in range(len(a)):
    for j in range(n):
        if j == a[i]:
            b[j-1] += 1

for i in range(n):
    print(b[i])

### FIXED CODE ###

n = int(input())
A = input().split()
a = [int(i) for i in A]
b = [0]*n

for i in range(len(a)):
    s = a[i]
    b[s-1] += 1

for i in range(n):
    print(b[i])
### BUGGY CODE ###

import heapq
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse=True)
F = sorted([int(i) for i in input().split()])

if sum(A) <= K:
    print(0)
    exit()
else:
    hq = []
    heapq.heapify(hq)  # リストhqのheap化

    for i in range(N):
        heapq.heappush(hq, (-(A[i]*F[i]), A[i], F[i]))  # heap化されたリストhqに要素xを追加

    for i in range(K):
        c, a, f = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力

        a -= 1
        heapq.heappush(hq, (-(a*f), a, f))

    c, a, f = heapq.heappop(hq)  # heap化されたリストhqから最小値を削除＆その最小値を出力
    print(-c)


### FIXED CODE ###

N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])
F = sorted([int(i) for i in input().split()], reverse=True)

if sum(A) <= K:
    print(0)
    exit()
else:
    OK = 10**12
    NG = -1

    while OK-NG > 1:
        mid = (OK+NG)//2
        cnt = 0

        for i, a in enumerate(A):
            cnt += max(0, a-mid//F[i])
        if cnt <= K:
            OK = mid
        else:
            NG = mid

print(OK)
### BUGGY CODE ###

p = int(input())
a = list(map(int,input().split()))

ans = [0]*p

for i in range(p):
    if a[i] == 1:
        ans[0] -= p-1
        m = 1
        for j in range(p):
            ans[p-1-j] -= m
            ans[p-1-j] %= p
            m *= (i %p)

print(*ans)        

### FIXED CODE ###

import sys
input = sys.stdin.readline

p = int(input())
a = [int(i) for i in input().split()]

ans = [0]*p

for i,j in enumerate(a):
    if j == 0:
        continue
    ans[0] -= p-1
    m = 1
    for k in range(p):
        ans[p-1-k] -= m
        ans[p-1-k] %= p
        m *= i
        m %= p

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

N, K = map(int, input().split())
dp = [0] *  (2 * 10 ** 5 + 1)
S = set()
for i in range(K):
    l, r = map(int, input().split())
    for v in range(l, r + 1):
        S.add(v)

dp[1] = 1
MOD = 998244353
for i in range(1, N):
    for v in S:
        if i + v <= N:
            dp[i + v] += dp[i]
            dp[i + v] %= MOD

print(dp[N])



### FIXED CODE ###

N, K = map(int, input().split())
W = [0] * (N + 1)
W[1] = 1

R = []
for i in range(K):
    l, r = map(int, input().split())
    R.append((l, r))

MOD = 998244353
for i in range(1, N):
    for l, r in R:
        a = max(i - r, 0)
        b = i - l
        if b < 0:
            continue
        W[i + 1] += (W[b + 1] - W[a])
        W[i + 1] %= MOD
    W[i + 1] += W[i]
    
print(W[N] - W[N - 1])
### BUGGY CODE ###

d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        for i in range(count, b+count):
            if i < N:
                tmp[i] = c
        count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

if __name__ == '__main__':
    main()





### FIXED CODE ###

d = input().split()
N = int(d[0])
M = int(d[1])
d = input().split()
As = [int(num) for num in d]
As.sort()


def main():
    lis = []
    for i in range(1, M+1):
        d = input().split()
        b = int(d[0])
        c = int(d[1])
        lis.append([c, b])
    lis = sorted(lis,key=lambda x:(-x[0], x[1]))
    count = 0
    asum = 0
    tmp = [0 for i in range(N)]
    for c, b in lis:
        if count < N:
            for i in range(count, b+count):
                if i < N:
                    tmp[i] = c
            count += b
    for i in range(N):
        if tmp[i] > As[i]:
            asum += tmp[i]
        else:
            asum += As[i]
    print(asum)
        

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

import fractions
k = int(input())
ans = 0

for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            g_ab = fractions.gcd(a ,b)
            g_abc = fractions.gcd(g_ab, c)
            if a != b != c:
                ans += g_abc * 6
            elif a == b == c:
                ans += g_abc
            else:
                ans += g_abc * 3
print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0

for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            g_ab = math.gcd(a ,b)
            g_abc = math.gcd(g_ab, c)
            if a != b != c:
                ans += g_abc * 6
            elif a == b == c:
                ans += g_abc
            else:
                ans += g_abc * 3
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

import heapq
from collections import defaultdict
import sys

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

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            heapq.heappush(h, (t+b, coin-a, neighbor))

    heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))

### FIXED CODE ###

import heapq
from collections import defaultdict
import sys

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

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

connect = defaultdict(list)
for i in range(m):
    u, v, a, b = map(int, input().split())
    connect[u].append((v, a, b))
    connect[v].append((u, a, b))

c, d = [-1], [-1]
for i in range(n):
    c_, d_ = map(int, input().split())
    c.append(c_)
    d.append(d_)

ans = [-1] * (n+1)
dp = [{} for _ in range(n+1)]
coin_max = [-1] * (n+1)

h = [(0, s, 1)]
heapq.heapify(h)

while heapq:
    t, coin, city = heapq.heappop(h)

    if ans[city] == -1:
        ans[city] = t
        if all([v >= 0 for v in ans[2:]]):
            break

    if coin not in dp[city]:
        dp[city][coin] = t
    else:
        continue

    if coin_max[city] >= coin:
        continue
    else:
        coin_max[city] = coin

    for neighbor, a, b in connect[city]:
        if coin - a >= 0 and neighbor != city:
            if coin-a not in dp[neighbor]:
                heapq.heappush(h, (t+b, coin-a, neighbor))

    if coin+c[city] not in dp[city]:
        heapq.heappush(h, (t+d[city], coin+c[city], city))

print('\n'.join(map(str, ans[2:])))
### BUGGY CODE ###

n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()

sub = 10 ** 9
for i in range(n-k+1):
    hmax = max(h[i:i+k])
    hmin = min(h[i:i+k])
    sub = min(hmax - hmin, sub)
print(sub)

### FIXED CODE ###

n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))
h.sort()

sub = 10 ** 9
for i in range(n-k+1):
    hmax = h[i+k-1]
    hmin = h[i]
    sub = min(hmax - hmin, sub)
print(sub)
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,x,y = map(int,input().split()) #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1

for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
k=0

for i in range(n):
    if i==0:
        continue
    for j in range(n):
        k=k+warshall_floyd(d)[j].count(i)
    print(k//2)
    k=0


### FIXED CODE ###

from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
import copy
from bisect import *

input = lambda: sys.stdin.readline().rstrip()

N, X, Y = map(int, input().split())
data = [[] for i in range(N + 1)]
for i in range(1, N):
    a = i
    b = i + 1
    data[a].append(b)
    data[b].append(a)
data[X].append(Y)
data[Y].append(X)

dic = defaultdict(int)
for i in range(1,N+1):
    stack=deque([[i,0]])
    visited=set()
    visited.add(i)
    count=set()
    while stack:
        now, dist=stack.popleft()
        for j in data[now]:
            if not j in visited:
                #print(stack)
                visited.add(j)
                stack.append([j,dist+1])
                dic[dist+1]+=1
for k in range(1,N):
    print(dic[k]//2)
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
INF = 1e10
def main():
    H,W=map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())

    S = [input() for _ in range(H)]

    def dijkstra(sx, sy):
        # Color = [[0]*(W) for _ in range(H)] # 0: 未訪問 1: Seen 2: Visited
        D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
        # P = [None]*N #親

        D[sx][sy] = 0
        # P[s] = None
        # PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。
        PQ = [(0, sx, sy)]
        heapify(PQ)
        while PQ: # PQに候補がある限り
            min_cost, ux, uy = heappop(PQ) # 最小コストなノードu
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    xx, yy = ux+dx, uy+dy
                    if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                        is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                        # neighborでなければコストが1増える
                        if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                            D[xx][yy] = D[ux][uy] + is_not_neighbor
                            heappush(PQ, (D[xx][yy], xx, yy))
        return D

    D = dijkstra(ch-1, cw-1)
    if D[dh-1][dw-1] >= INF:
        print(-1)
    else:
        print(D[dh-1][dw-1])

main()

### FIXED CODE ###

import heapq
INF = 1e7
H,W=map(int, input().split())
sx, sy = map(int, input().split())
dh, dw = map(int, input().split())
sx -= 1
sy -= 1
S = [input() for _ in range(H)]
D = [[INF]*(W) for _ in range(H)] #始点からの距離(重み)
D[sx][sy] = 0
PQ = [(0, (sx, sy))]
heapq.heapify(PQ)
while PQ: # PQに候補がある限り
    _, (ux, uy) = heapq.heappop(PQ) # 最小コストなノードu
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            xx, yy = ux+dx, uy+dy
            if 0 <= xx < H and 0 <= yy < W and S[xx][yy]==".":
                is_not_neighbor = int(abs(dx) + abs(dy) != 1)
                # neighborでなければコストが1増える
                if D[ux][uy] + is_not_neighbor < D[xx][yy]:
                    D[xx][yy] = D[ux][uy] + is_not_neighbor
                    heapq.heappush(PQ, (D[xx][yy], (xx, yy)))
if D[dh-1][dw-1] >= INF:
    print(-1)
else:
    print(D[dh-1][dw-1])
### BUGGY CODE ###

N=int(input())
A=input()
A=A.split()
for i in range(N):
  A[i]=int(A[i])

X=[]
for i in range(N):
  for j in range(i+1,N):
    X.append(A[i]*A[j])
x=sum(X)

MOD=1000000007
print(x%MOD)



### FIXED CODE ###

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

S=sum(A)
a=0
for x in A:
  S-=x
  a+=S*x
    
MOD=10**9+7
print(int(a%MOD))
### BUGGY CODE ###

N = int(input())
 
for n in range(1,N+1):
  ans = 0
  check = False
  for x in range(1,100):
    for y in range(x,100):
      for z in range(y,100):
        if (x**2 + y**2 + z**2 + x*y + y*z + z*x) == n:
          if x == y and y == x and z == x:
            ans += 1
          elif x == y  or z == x or y == z:
            ans += 3
          elif x != y and y != z and z != x:
            ans += 6
  print(ans)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10001)]

for i in range(1,101):
  for j in range(1,101):
    for k in range(1,101):
      v = i*i + j*j + k*k + i*j + j*k + k*i
      if v < 10001:
        ans[v] += 1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

nc, ac, bc = map(int, input().split())

n = nc - 1
a = ac - 1
b = bc - 1

if (b - a) % 2 == 0:
    print((b - a) // 2)
else:
    left = a
    right = n - b
    if left <= right:
        ran = b - a
        flag = 0
        ans = 0
        while (ran % 2 != 0):
            b -= 1
            if a != 0:
                a -= 1
            else:
                if flag == 0:
                    flag = 1
                else:
                    a += 1
            ran = b - a
            ans += 1
        print(ans + (ran // 2))
    else:
        ran = b - a
        flag = 0
        ans = 0
        while (ran % 2 != 0):
            a += 1
            if b != n:
                b += 1
            else:
                if flag == 0:
                    flag = 1
                else:
                    b -= 1
            ran = b - a
            ans += 1
        print(ans + (ran // 2))

### FIXED CODE ###

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


if (b - a) % 2 == 0:
    print((b - a) // 2)
else:
    test = (b - a) // 2
    left = a - 1
    right = n - b
    if left >= right:
        print(n - a - test)
    else:
        print(b - 1 - test)
### BUGGY CODE ###

n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(2,int(pow(p,1/n))+2):
        x=i**n
        if x>p:
            break
        if p%x==0:
            res=i
print(res)


### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
### BUGGY CODE ###

s = input()
tmp = 0
for idx, n in enumerate(s):
	if n=='A': 
		for idxx, nn in enumerate(s[-1:idx:-1]):
			if nn=='Z':
				tmp = max((len(s)-idxx)-idx, tmp)
		
print(tmp)

### FIXED CODE ###

"""
一番左のaの位置と一番右のzの位置だけわかればよい
"""
s = input()
a = s.index('A')
z = len(s)-s[::-1].index('Z')
print(z-a)
### BUGGY CODE ###

import math

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

total = 1
for a in li:
  total *= a
  
if math.pow(10,18) < total:
  total = -1
  
print(total)

### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

def resolve():
	# DP[i+1][j]: i=品物[0:i]の中から, j: 合計jを超えない範囲で選んだ品物の, value=価値の総和の最大値
	# DP[0][j] = 0
	# DP[i+1][j] = DP[i][j] (if j < w_n)
	# DP[i+1][j] = max( DP[i][j], DP[i][j-w_n] + v_n )

	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# print(f'N={N}, W={W}', file=sys.stderr)
	# DP配列の宣言
	dp = [[0] * (W+1) for _ in range(N+1)]
	# print(f'DP.shape=', np.array(dp).shape, file=sys.stderr)
	# DP初期化: dp[0][w] = 0 -> 済み
	# i = 商品番号
	for i in range(N):
		# w_n: 品物[n]の重さ, v_n: 品物[n]の価値
		w_n, v_n = map(int, input().split())
		# j = バッグに入る残り容量
		for j in range(1, W+1):
			# print(f'{i},{j},{w_n},{v_n}', file=sys.stderr)
			# バッグに入る残り容量が品物[i]の重さw_nより大きい場合
			if j >= w_n:
				dp[i+1][j] = max(
					dp[i][j-w_n]+v_n,	# バッグに入れた時の価値
					dp[i][j]			# バッグにいれない時の価値
				)
			else:
				dp[i+1][j] = dp[i][j]	# バッグに入れない
	# 価値の最大値を出力
	print(dp[N][W])
resolve()

### FIXED CODE ###

import numpy as np
def resolve():
	# N: 品物の個数、W: 容量の上限
	N, W = map(int, input().split())
	# DP配列の宣言: DP[N][W]
	dp = np.empty((N+1, W+1), dtype=np.int64)
	# DP配列の初期化
	dp[0,:] = 0
	for i in range(N):
		w_n, v_n = map(int, input().split())
		dp[i+1, :w_n] = dp[i, :w_n]
		dp[i+1, w_n:] = np.maximum(
			dp[i, w_n:],
			dp[i, :(W+1-w_n)] + v_n
		)
	print(dp[N, W])
resolve()