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

#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

dp = [[0] * (W + 1) for _ in range(N + 1)]
for i, (w, v) in enumerate(x, start=1):
    dp_i = dp[i]
    dp_im = dp[i - 1]
    for j in range(1, W + 1):
        if j < w:
            dp_i[j] = dp_im[j]
        else:
            a = dp_im[j - w] + v
            b = dp_im[j]
            if a > b:
                dp_i[j] = a
            else:
                dp_i[j] = b
 
ans = dp[-1][-1]
print(ans)


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

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

import sys
input = sys.stdin.readline
input()
A = input().split()
if "0" in A:
    print(0)
    quit()
ans = 1
for a in A:
    ans*=int(a)
print(-1 if ans>10**18 else ans)

### FIXED CODE ###

input()
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    quit()
else:
    prod = 1
    for a in A:
        prod*=a
        if prod > 10**18:
            print(-1)
            quit()
    print(prod)
### BUGGY CODE ###

import queue
N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

visited = [False] * N
rooms = [-1] * N
def bfs(u):
    q = queue.Queue()
    q.put((u, -1))
    while not q.empty():
        (v, p) = q.get()
        visited[v] = True
        if p != -1 and rooms[v] == -1:
            rooms[v] = p
        for e in edges[v]:
            if visited[e]:
                continue
            q.put((e, v))

bfs(0)
print("Yes")
for x in rooms[1:]:
    print(x + 1)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

rooms = [-1] * N
def bfs(u):
    q = deque()
    q.append(u)
    while 0 < len(q):
        v = q.popleft()
        for e in edges[v]:
            if rooms[e] == -1:
                rooms[e] = v + 1
                q.append(e)

bfs(0)
print("Yes")
print(*rooms[1:], sep="\n")
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
AI = [i + a for i, a in enumerate(A)]
AJ = [i - a for i, a in enumerate(A)]

count = 0
for k in range(0, max(A)+2*10**5):
    ci = AI.count(k)
    cj = AJ.count(k)
    count += ci * cj
print(count)

### FIXED CODE ###

N = int(input())
A = tuple(map(int, input().split()))
AI = tuple(i + a for i, a in enumerate(A))
AJ = tuple(i - a for i, a in enumerate(A))

cai = {}
caj = {}
vali = set()
valj = set()
for ai, aj in zip(AI, AJ):
    if not ai in cai:
        cai[ai] = 0
    if not aj in caj:
        caj[aj] = 0

    cai[ai] += 1
    vali.add(ai)

    caj[aj] += 1
    valj.add(aj)

count = 0
for val in vali & valj:
    count += cai[val] * caj[val]

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

n = int(input())
ans = 0

for i in range(n):
    ans += i
    
print(ans)


### FIXED CODE ###

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

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

def resolve():
	s = input()
	w = ['dream', 'dreamer', 'erase', 'eraser']
	for i in range(len(w)):
		w[i] = w[i][::-1]
	s = s[::-1]
	c = ''
	for i in s:
		c += i
		if c in w:
			c = ''
	if not len(c):
		print('YES')
	else:
		print('NO')
resolve()

### FIXED CODE ###

def resolve():
	s = input()
	w = ['dream', 'dreamer', 'erase', 'eraser']
	h = dict()
	for i in range(len(w)):
		h[w[i][::-1]] = True
	s = s[::-1]
	c = ''
	for i in s:
		c += i
		if h.get(c):
			c = ''
	if not len(c):
		print('YES')
	else:
		print('NO')
resolve()
### BUGGY CODE ###

A = 0






S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

from collections import defaultdict
from bisect import bisect_right

def sol():
    S = input()
    T = input()

    setS = set(S)
    setT = set(T)
    for t in setT:
        if not t in setS:
            print('-1')
            return

    posS = defaultdict(list)

    for i, s in enumerate(S):
        posS[s].append(i)

    for s in enumerate(S):
        posS[s].sort()

    prev = -1
    ans = 0
    N = len(S)

    for t in T:
        next = bisect_right(posS[t], prev)
        if next >= len(posS[t]):
            ans += N - prev
            ans += posS[t][0]
            prev = posS[t][0]
        else:
            ans += posS[t][next] - prev
            prev = posS[t][next]

    print(ans)

sol()
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	L = LI();L.sort();L=np.array(L);
	#a<=b<=c
	ans = 0
	for i in range(N-1):
		for j in range(i+1,N):
			a,b = L[i],L[j]
			ch=(L>=b)&(L<(a+b))
			ch[[i,j]]=False
			ans +=  np.sum(ch)
	print(ans)

main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	L = LI();L.sort();
	#a<=b<=c

	def BS(a,c,i,j):
		s,t = i,j
		while s+1 < t:
			mid = (s+t)//2
			if (a+L[mid]>c):
				t = mid
			else:
				s = mid
		return j-t


	ans = 0

	for i in range(N-1):
		for j in range(i+2,N):
			a = L[i]
			c = L[j]
			ans += BS(a,c,i,j)

	print(ans)

main()
### BUGGY CODE ###

import math
n,m = map(int,input().split())
a = list(map(int,input().split()))

s = []
k = 0
for i in range(0,n):
    k += a[i]
    s.append(k)

for i in range(0,n):
    s[i] = s[i]%m

d = [0]
ass = 0
w = s.count(0)
ass += w*(w+1)//2

for i in range(0,n):
    if s[i] not in d:
        d.append(s[i])
        w = s.count(s[i])
        if w != 1:
            ass += w*(w-1)//2

print(ass)

### FIXED CODE ###

import bisect
n,m = map(int,input().split())
a = list(map(int,input().split()))

s = []
k = 0
for i in range(0,n):
    k += a[i]
    s.append(k%m)

ass = 0
w = s.count(0)
ass += w*(w+1)//2
s.sort()

hj = w
while hj <= n-1:
    jkl = bisect.bisect_right(s,s[hj])
    w = jkl - hj
    if w != 1:
        ass += w*(w-1)//2
    hj = jkl
print(ass)
### BUGGY CODE ###

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

# DP
INF = int(1e10)
dp = [INF] * N
dp[0] = 0


for i in range(1, N):
    for j in range(1, K+1):
        if i-j >= 0:
            dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))
        else:
            break
print(dp[N-1])

### FIXED CODE ###

# Educational DP Contest B-Frog 2

def frog(N, K, h):
    # initialize
    inf = float('inf')
    dp = [inf] * N
    
    minKN = min(K, N)
    for i in range(minKN):
        if i == 0:
            dp[i] = 0
        else: 
            dp[i] = abs(h[0] - h[i])
            for j in range(minKN):
                if j == i:
                    continue
                elif j < i:
                    dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
    # DP
    for i in range(N):
        if i == 0:
            continue
        elif i < K:
            continue
        else:
            dp[i] = min([abs(h[k] - h[i]) + dp[k] for k in range(i-K, i)])
    return dp[N-1]
    
if __name__ == "__main__":
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    print(frog(N, K, h))
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0 for i in range(n+1)]
    searched[s] = 1
    while len(Q) != 0:
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans *= cand
            cand -= 1
            Qappend(i)
        ans = ans % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


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

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp=[[[0]*3 for i in range(s+1)] for j in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp[i+1][j][1]=(dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1])%mod
      dp[i+1][j][2]=(dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1]+dp[i][j][2])%mod
    else:
      dp[i+1][j][0]=dp[i][j][0]%mod
      dp[i+1][j][1]=(dp[i][j][1]+dp[i][j][0])%mod
      dp[i+1][j][2]=(dp[i][j][2]+dp[i][j][1]+dp[i][j][0])%mod
print(dp[n][s][2])

### FIXED CODE ###

n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0 for i in range(s+1)] for j in range(n+1)]
dp1=[[0 for i in range(s+1)] for j in range(n+1)]
dp2=[[0 for i in range(s+1)] for j in range(n+1)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
b = []
for i in range(N):
  b.append(a[i])
  b.reverse()
print(' '.join(map(str,b)))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
b = [0]*N
if N % 2 == 0:
  for i in range(N):
    if (i+1) %2 == 1:
      b[N//2+(i+1)//2] = a[i]
    else:
      b[N//2-(i+1)//2] = a[i]
else:
  for i in range(N):
    if (i+1) %2 == 1:
      b[(N-1)//2-(i+1)//2] = a[i]
    else:
      b[(N-1)//2+(i+1)//2] = a[i]
print(' '.join(map(str,b)))
### BUGGY CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
num=[1]
M=10**9+7
for i in range(n):
    x=(num[i]*(i+1))%M
    num.append(x)
def inverse(number,mod):
    m=mod-2
    mod2=""
    while m!=0:
        if m%2==0:
            mod2="0"+mod2
        else:
            mod2="1"+mod2
        m=m//2
    two=[]
    for i in range(len(mod2)):
        if mod2[len(mod2)-1-i]=="1":
            two.append(i)
    ret=1
    for i in two:
        v=i
        retsub=number
        while v>0:
            retsub=retsub**2
            retsub=retsub%mod
            v-=1
        ret*=retsub
    ret=ret%mod
    return ret
def comb(p,q):
    ret1=num[p]
    ret2=inverse(num[p-q],M)
    ret3=inverse(num[q],M)
    ret=(ret1*ret2*ret3)%M
    return ret
#min
minsum=0
for i in range(n):
    if n-(i+1)>=k-1:
        minsum+=(a[i] * comb(n-i-1,k-1))%M
        minsum%=M
b=sorted(a,reverse=True)
#max
maxsum=0
for i in range(n):
    if n-(i+1)>=k-1:
        maxsum+=(b[i] * comb(n-i-1,k-1))%M
        maxsum%=M
print((maxsum-minsum)%M)


### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
num=[1]
M=10**9+7
for i in range(n):
    x=(num[i]*(i+1))%M
    num.append(x)
def inverse(number,mod):
    m=mod-2
    mod2=""
    while m!=0:
        if m%2==0:
            mod2="0"+mod2
        else:
            mod2="1"+mod2
        m=m//2
    two=[]
    for i in range(len(mod2)):
        if mod2[len(mod2)-1-i]=="1":
            two.append(i)
    ret=1
    for i in two:
        v=i
        retsub=number
        while v>0:
            retsub=retsub**2
            retsub=retsub%mod
            v-=1
        ret*=retsub
    ret=ret%mod
    return ret
def comb(p,q):
    ret1=num[p]
    ret2=inverse(num[p-q],M)
    ret3=inverse(num[q],M)
    ret=(ret1*ret2*ret3)%M
    return ret
#min
minsum=0
for i in range(n):
    if n-(i+1)>=k-1:
        minsum+=(a[i] * comb(n-i-1,k-1))%M
        minsum%=M
b=sorted(a,reverse=True)
#max
maxsum=0
for i in range(n):
    if n-(i+1)>=k-1:
        maxsum+=(b[i] * comb(n-i-1,k-1))%M
        maxsum%=M
print((maxsum-minsum)%M)
### BUGGY CODE ###

n = int(input())
factor = []
tmp = n
for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
if tmp != 1:
    factor.append(tmp)
w = len(factor)
if w == 0:
    factor.append(n)
    w = 1
if w == 1:
    print(n - 1)
else:
    # bit = [0] * w
    ans = 1000000000000
    for i in range(1, 2 ** w):
        a, b = 1, 1
        for j in range(w):
            # bit[j] = i & (2 ** j)
            if i & (2 ** j) == 0:
                a *= factor[j]
            else:
                b *= factor[j]
        if a + b - 2 < ans:
            ans = a + b - 2
        # print(i, bit, a, b, ans)
    print(ans)

### FIXED CODE ###

n = int(input())
ans = 1000000000000
for i in range(1, int(n ** 0.5) + 1):
    if n % i == 0:
        a = i
        b = n // i
        ans = min(ans, a + b - 2)
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())	

al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al = sorted(al)
bl = sorted(bl)
cl = sorted(cl)
rank = []
for xx in range(x-1,-1,-1):
    for yy in range(y-1, -1, -1):
        for zz in range(z-1,-1,-1):
            if len(rank) < k:
                rank.append(al[xx]+bl[yy]+cl[zz])
                rank = sorted(rank, reverse=True)
            else:
                tmp = al[xx]+bl[yy]+cl[zz]
                if rank[-1] < tmp:
                    rank.pop()
                    rank.append(tmp)
                    rank = sorted(rank, reverse=True)
                else:
                    break

for i in rank:
    print(i)
                
            
            

### FIXED CODE ###

x,y,z,k = map(int,input().split())	

al = list(map(int,input().split()))
bl = list(map(int,input().split()))
cl = list(map(int,input().split()))

al = sorted(al)
bl = sorted(bl)
cl = sorted(cl)
rank = []
flag = False
for xx in range(x-1,-1,-1):
    tmp = al[xx]+bl[-1]+cl[-1]
    if flag and rank[-1] >= tmp:
        break
    for yy in range(y-1, -1, -1):
        tmp = al[xx]+bl[yy]+cl[-1]
        if flag and rank[-1] >= tmp:
            break
        for zz in range(z-1,-1,-1):
            if len(rank) < k:
                rank.append(al[xx]+bl[yy]+cl[zz])
                rank = sorted(rank, reverse=True)
            else:
                tmp = al[xx]+bl[yy]+cl[zz]
                if rank[-1] < tmp:
                    flag = True
                    rank.pop()
                    rank.append(tmp)
                    rank = sorted(rank, reverse=True)
                else:
                    break

for i in rank:
    print(i)
### BUGGY CODE ###

def strTint(s):
    return ord(s)-96

alpha = {}
for i in range(97,97+26):
    alpha[chr(i)] = i - 96

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    
    b = 27
    mod1 = 10**9+7
    mod2 = 10**9+9
    D = {}
    for i in range(N):
        H = strTint(S[i])
        H1 = H%mod1
        #H2 = H%mod2
        if not H1 in D:
            D[H1] = [1,i,i]
        for j in range(i+1,min(i+N//2+2,N)):
            H1 = (H1*b + strTint(S[j]))%mod1
            if not H1 in D:
                D[H1] = [j-i+1,i,i]
            else:
                D[H1][-1] = i
    
    ans = 0
    for i in D:
        L = D[i][0]
        tmp = 0
        if D[i][1] + L <= D[i][-1] and ans < L:
            ans = L
    g = time.time()
    #print(g-star)
    print(ans)
    
main()

### FIXED CODE ###

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

def main():
    N = int(input())
    S = input()
    #N = 5000
    #S = "a"*N
    import time
    star = time.time()
    A = [[] for i in range(N)]
    for i in range(N):
        A[i] = [0]*i + z_algo(S[i:])
    ans = 0
    for i in range(N):
        for j in range(N):
            if i + A[i][j] <= j and ans < A[i][j]:
                ans = A[i][j]
    
    g = time.time()
    #print(g-star)
    print(ans)
    
main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    DP = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            DP[i+1][j] = DP[i][j]
            if j-w[i] >= 0:
                DP[i+1][j] = max(DP[i+1][j], DP[i][j-w[i]]+v[i])
    print(DP[N][W])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    DP = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            DP[i+1][j] = DP[i][j]
            if j-w[i] >= 0:
                DP[i+1][j] = max(DP[i+1][j], DP[i][j-w[i]]+v[i])
    print(DP[N][W])
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)


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

import sys
import math
import statistics
import itertools
from collections import deque
n=int(input())
#n,m=map(int,input().split()))
#lis=list(map(int,input().split()))
#side=[]
#for _ in range(m):
    #side.append(tuple(map(int,input().split())))
ans_lis =[0]*1000000

#per_lis=itertools.permutations(list(range(1,4)))


def f(a):
    A=int(math.sqrt(a))
    cnt=0
    for i in range(1,A+1):
        for j in range(1,A+1):
            for k in range(1,A+1):
                tmp=i**2+j**2+k**2+i*j+j*k+k*i
                if tmp==a:
                    cnt+=1
    return cnt
for i in range(1,n+1):
    print(f(i))

### FIXED CODE ###

import sys
import math
import statistics
import itertools
from collections import deque
N=int(input())

ans_lis =[0]*10000000


nn=math.sqrt(N)
n=int(nn)
#per_lis=itertools.permutations(list(range(1,4)))
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            tmp=0
            tmp=i**2+j**2+k**2+i*j+j*k+k*i
            ans_lis[tmp-1]+=1
for g in range(N):
    print(ans_lis[g])
### BUGGY CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))

### FIXED CODE ###

import copy
import sys
H, W, M= map(int,input().split())
height = [0]*H
width = [0]*W
object = []
for s in sys.stdin.readlines():
    h, w = map(int, s.split())
    height[h-1] += 1
    width[w-1] += 1
    object.append([h-1, w-1])
h_max = max(height)
w_max = max(width)
cand_w = []
cand_h = []
for i in range(W):
   if width[i] == w_max:
      cand_w.append(i)
for i in range(H):
   if height[i] == h_max:
      cand_h.append(i)
ans = h_max + w_max
c = 0
p = len(cand_h)*len(cand_w)
cand_h = set(cand_h)
cand_w = set(cand_w)
if M >= p:
   for i in range(len(object)):
      if object[i][0] in cand_h and object[i][1] in cand_w:
         c += 1
print(ans - (c == p))