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

H, W, M = map(int, input().split())
h_list = [0] * H
w_list = [0] * W
hw_list = [[0 for i in range(W)] for j in range(H)]
for _ in range(M):
  h, w = map(int, input().split())
  h_list[h-1] += 1
  w_list[w-1] += 1
  hw_list[h-1][w-1] += 1

h_max = max(h_list)
w_max = max(w_list)
h_max_list = [i for i, v in enumerate(h_list) if v == max(h_list)]
w_max_list = [i for i, v in enumerate(w_list) if v == max(w_list)]

ok_flag = -1
for h in h_max_list:
  for w in w_max_list:
    if hw_list[h][w] == 0:
      ok_flag = 0
      break
print(h_max+w_max+ok_flag)

### FIXED CODE ###

H, W, M = map(int, input().split())
h_list = [0] * H
w_list = [0] * W
target = []
for _ in range(M):
  h, w = map(int, input().split())
  h_list[h-1] += 1
  w_list[w-1] += 1
  target += [[h-1,w-1]]

h_max = max(h_list)
w_max = max(w_list)
h_max_list = set([i for i, v in enumerate(h_list) if v == h_max])
w_max_list = set([i for i, v in enumerate(w_list) if v == w_max])

place = len(h_max_list) * len(w_max_list)
candidate = 0
for h,w in target:
  if (h in h_max_list) and (w in w_max_list):
    candidate +=1

print(h_max+w_max-(place == candidate))
### BUGGY CODE ###

def resolve():
    numbers = int(input())
    number_list = list(map(int, input().split()))
    answer = 0
    for i in range(numbers - 1):
        num1 = number_list[i]
        for j in range(numbers-i-1):
            answer += num1*number_list[i+j+1]
    print(answer%1000000007)
resolve()

### FIXED CODE ###

def resolve():
    numbers = int(input())
    number_list = list(map(int, input().split()))
    answer = 0
    num2 = sum(number_list)
    for num1 in number_list:
        num2 = num2 - num1
        answer += num1*num2
    print(answer%1000000007)
resolve()
### BUGGY CODE ###

import collections
import copy

n = int(input())
al = [int(x) for x in input().split()]
cs_orig = dict(collections.Counter(al))
copy_copy = copy.copy

aset = set(al)
patterns_d = {}

for i in range(1, n+1):
    cs = copy_copy(cs_orig)
    patterns = 0
    if i in aset:
        cs[i] -= 1
        for count in cs.values():
            if count > 1:
                patterns += int(count * (count - 1) / 2)

        patterns_d[i] = patterns

for a in al:
    print(patterns_d[a])


### FIXED CODE ###

import collections

n = input()
al = tuple(x for x in input().split())
aset = set(al)

# {number: count}
ccc = collections.Counter
counts_d = ccc(al)

# Count of count
v_counts = ccc(v for v in counts_d.values())

whole_patterns = sum(
    (int(k * (k - 1) / 2)) * v for k, v in v_counts.items() if k > 1
)

[print(whole_patterns - counts_d[a] + 1) for a in al]
### BUGGY CODE ###

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

dp = [0] * N

for i in range(1, N):
    m = math.inf
    for j in range(1, K+1):
        k = i - j
        if k < 0:
            break
        m = min(m, abs(h[i] - h[k]) + dp[k])
    dp[i] = m
print(dp[N-1])
    

### FIXED CODE ###

import math
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * N

for i in range(1, N):
    m = math.inf
    for j in range(1, K+1):
        k = i - j
        if k < 0:
            break
        m = min(m, abs(h[i] - h[k]) + dp[k])
    dp[i] = m
print(dp[N-1])
### BUGGY CODE ###

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

for i in range(1, n, 2):
    if a_list.count(n - i) != 2:
        print(0)
        exit()

if n % 2 != 0:
    if a_list.count(0) != 1:
        print(0)
        exit()
    else:
        print(2 ** -(-(len(a_list) - 1) // 2))
else:
    print(2 ** (len(a_list) // 2))

### FIXED CODE ###

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

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))
### BUGGY CODE ###

from sys import exit
N = int(input())
n = int(N ** 0.5)
for i in range(n, N + 1):
  if N % i == 0:
    ans = i + N // i - 2
    print(ans)
    exit()

### FIXED CODE ###

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

#encoding utf-8

import numpy as np

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

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

p = []
q = []

for i in range(Q):
    pa, qa = map(int, input().split())
    p.append(pa)
    q.append(qa)

EXP_map = np.zeros((N,N))
for i in range(M):
    EXP_map[L[i]-1][R[i]-1] += 1

def Answer(i):
    return int(EXP_map[(p[i]-1):(q[i]),(p[i]-1):(q[i])].sum())

for i in range(Q):
    print(Answer(i))


### FIXED CODE ###


N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)>>1)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)>>1,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in range(1,N+2):

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])
### BUGGY CODE ###

#test.py
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
                ans += gcd(i,j,k)

print(ans)
#メモ化再帰で高速化できないか考える
# Kまでの数の組み合わせを考える





### FIXED CODE ###

#test.py
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            if i==1 or j==1 or k ==1:
                ans += 1
            else:
                ans += gcd(i,j,k)

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

n = int(input())
a = list(map(int,input().split()))
c = 'YES'

for i in range(n-1) :
    b = a[1:]
    if a[0] in b :
        c = 'NO'
        break
    else :
        a = b.copy()
print(c)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
a.sort()
c = 'YES'

for i in range(n-1) :
    if a[i] == a[i+1] :
        c = 'NO'
        break
print(c)
### BUGGY CODE ###

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

count = [0]*n

for i in range(n):
#  print("i is", i,"=======")
  for j in range(i, n-1):
 #   print("h[j] is", h[j])
 #   print("h[j+1] is", h[j+1])
    if h[j] >= h[j + 1]:
      count[i] += 1
  #    print("count is",count)
    else:
      break

max_cnt = sorted(count, reverse = True)
print(max_cnt[0])

  

### FIXED CODE ###

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

n = int(input())
contador = 0
res = 0
while(True):
    contador += 1
    if contador % 2 == 0 and contador % n == 0:
        res = contador
        break;
print(res,'\n')

### FIXED CODE ###

def main():
    a, b = 2, int(input())
    ta, tb = a, b
    if b == 0: print(0)
    while a%b != 0:
       a, b = b, a%b
    print(int((ta*tb)/b))
main()
### BUGGY CODE ###

N,M,K=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
CD=[[] for _ in range(N)]
for _ in range(K):
  c,d=map(int,input().split())
  CD[c-1].append(d)
  CD[d-1].append(c)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i+1 not in CD[x] and [i+1,x+1] not in AB and [x+1,i+1] not in AB]
      
uf=UnionFind(N)
for i in range(M):
  uf.union(AB[i][0]-1,AB[i][1]-1)

ans=[0]*N
for i in range(N):
  ans[i]=len(uf.members(i))-1 
print(*ans)

### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
      
uf=UnionFind(N)
for i in range(N):
  for j in AB[i]:
    uf.union(i,j-1)

ans=[0]*N
for i in range(N):
  ans[i]=uf.size(i)-1-len(AB[i])
for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    ans[c-1]-=1
    ans[d-1]-=1
print(*ans)
### BUGGY CODE ###

n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
frsiz={i:len(relfr[i]) for i in range(n)}
cand={0}
searched=set()
gr=set()
all_gr={i for i in range(n)}
ans=[0]*n
c=0
while True:
  siz=0
  while True:
    now=cand.pop()
    gr.add(now)
    c+=1
    siz+=1
    for point in relfr[now].difference(gr,cand):
      cand.add(point)
    if len(cand)==0:
      break
  for i in gr:
    ans[i]=siz-frsiz[i]-len(relbl[i].intersection(gr))-1
    searched.add(i)
  all_gr=all_gr.difference(searched)
  gr.clear()
  if c!=n:
    cand.add(list(all_gr)[0])
  else:
    break
print(' '.join(map(str,ans)))

### FIXED CODE ###

n,m,k=map(int,input().split())
relfr={i:set() for i in range(n)}
relbl={i:set() for i in range(n)}
for i in range(m):
  a,b=map(int,input().split())
  relfr[a-1].add(b-1)
  relfr[b-1].add(a-1)
for i in range(k):
  a,b=map(int,input().split())
  relbl[a-1].add(b-1)
  relbl[b-1].add(a-1)
blsiz=[0 for i in range(n)]
ans=[0]*n
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
uf=UnionFind(n)
for i in range(n):
  for j in relfr[i]:
    uf.Unite(i,j)
for i in range(n):
  for j in relbl[i]:
    if uf.isSameGroup(i,j):
      blsiz[i]+=1
for i in range(n):
  ans[i]=uf.Count(i)-len(relfr[i])-blsiz[i]-1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    a = k[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
for key in d:
    a = d[key]
    dd[key] = int(a*(a-1)/2)
for i in range(N):
    res = 0
    for key in d:
        if d[key]>1:
            if key != k[i]:
                res += dd[key]
            else:
                a = d[key]
                res += int((a-1)*(a-2)/2)
    print(res)

### FIXED CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    a = k[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
tot = 0
for key in d:
    a = d[key]
    dd[key] = int(a*(a-1)/2)
    tot += dd[key]
for i in range(N):
    print(tot - d[k[i]]+1)
### BUGGY CODE ###

N = int(input())
S = input()
part = 0
leftW = 0
rightR = S.count('R')
moves = [rightR]

for i in range(N):
	leftW = S[:i+1].count('W')
	rightR = S[i+1:].count('R')
	moves.append(max(leftW, rightR))
# print(moves)
ans = min(moves[i] for i in range(N+1))
print(ans)


### FIXED CODE ###

N = int(input())
S = input()
part = 0
leftW = 0
rightR = S.count('R')
moves = [rightR]

for i in range(N):
	if S[i] == 'R':  # rightR:decrease
		rightR -= 1
	else:          # leftW:increase
		leftW += 1
	moves.append(max(leftW, rightR))
# print(moves)
ans = min(moves[i] for i in range(N+1))
print(ans)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count ** 11 > N ** 10 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

N = int(input())

def pToHW(p):
    p = int(p) - 1
    return divmod(p, N)

P = list(map(pToHW, input().split()))
INF = 10**18

minDist = [[INF] * N for _ in range(N)]
isFilled = [[True] * N for _ in range(N)]

def dfs(h, w):
    st = [(h, w)]
    while st:
        h, w = st.pop()
        dist = minDist[h][w] + (1 if isFilled[h][w] else 0)
        for toH, toW in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if 0 <= toH < N and 0 <= toW < N:
                if minDist[toH][toW] > dist:
                    minDist[toH][toW] = dist
                    st.append((toH, toW))

for h in range(N):
    for w in range(N):
        minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

ans = 0
for h, w in P:
    ans += minDist[h][w]
    isFilled[h][w] = False
    dfs(h, w)
print(ans)


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ma = 10**18
ans = 1
for i in a:
    ans = ans * i
if ans > ma:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if 0 in a:
    print(0)
else:
    ma = 10**18
    ans = 1
    for i in a:
        ans = ans * i
        if ans > ma:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

n=int(input())
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

def f(i,j,k):
    if i==j==k==0:
        return
    res=n
    if i>0:
        res+=dp[i-1][j][k]*i
    if j>0:
        res+=dp[i+1][j-1][k]*j
    if k>0:
        res+=dp[i][j+1][k-1]*k
    res*=l[i+j+k]
    dp[i][j][k]=res
    return

l=[1]
for i in range(1,1000):
    l.append(1.0/i)
for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            f(i,j,k)
print(dp[p][q][r])


### FIXED CODE ###

n=int(input())
dp=[[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

l=[1]
for i in range(1,1000):
    l.append(1.0/i)

for k in range(r+1):
    for j in range(q+r-k+1):
        for i in range(n-k-j+1):
            if i==j==k==0:
                continue
            res=n
            if i>0:
                res+=i*dp[i-1][j][k]
            if j>0:
                res+=j*dp[i+1][j-1][k]
            if k>0:
                res+=k*dp[i][j+1][k-1]
            res*=1/(i+j+k)
            dp[i][j][k]=res

print(dp[p][q][r])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

s=input()
def roopR(l,n):
  if s[l]=='L':
    if n%2==0:
      return l
    else:
      return l-1
  else:
    return roopR(l+1,n+1)

def roopL(l,n):
  if s[l]=='R':
    if n%2==0:
      return l
    else:
      return l+1
  else:
    return roopL(l-1,n+1)

a=len(s)
endlist=[]
for j in range(a):
  endlist.append(0)
for k in range(a):
  if s[k]=='R':
    b=roopR(k,0)
    endlist[b] += 1
  else:
    b=roopL(k,0)
    endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
### BUGGY CODE ###

n = int(input())
x = input()
#xx = int('0b' + x, 0)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

for i in range(n):
    if x[i] == '1':
        print(f(int('0b' + x[:i] + '0' + x[i+1:], 0)))
    else:
        print(f(int('0b' + x[:i] + '1' + x[i+1:], 0)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

n = int(input())
x = input()

c1 = x.count('1')
if c1 > 1:
    cc1 = int('0b' + x, 0) % (c1 - 1)
cc2 = int('0b' + x, 0) % (c1 + 1)

def f(n):
    ans = 0
    while n > 0:
        ans += 1
        n = n % bin(n).count('1')
    return ans

if c1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        else:
            print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
    exit()

for i in range(n):
    if x[i] == '1':
        print(f((-pow(2, n-i-1, c1-1) + cc1) % (c1 - 1)) + 1)
    else:
        print(f((pow(2, n-i-1, c1+1) + cc2) % (c1 + 1)) + 1)
### BUGGY CODE ###

# coding: utf-8
import sys
import numpy as np

N, W = map(int, sys.stdin.buffer.readline().split())
w, v = np.zeros(N+10, dtype=int), np.zeros(N+10, dtype=int)

for i in range(1, N+1):
    w[i], v[i] = map(int, sys.stdin.buffer.readline().split())
   
dp = np.zeros((N+1, W+1), dtype=int)

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

# for i in range(N+1):
#     print(dp[i])

print(dp[N,W])

### FIXED CODE ###

def main():
    N, W = map(int, input().split())
 
    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))
 
 
main()