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

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
n,q=map(int,input().split())
edges=[[] for i in range(n)]
inp=sys.stdin.buffer.readlines()
for i in inp[:n-1]:
    a,s=map(int,i.split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in inp[n-1:]:
    a,s=map(int,_.split())
    add[a-1]+=s


def f(x):
    if cnt[x]!=-1:return 
    ret=add[x]
    fd=0
    for to in edges[x]:
        if cnt[to]!=-1:ret+=cnt[to];fd=to;break
    cnt[x]=ret
    for to in edges[x]:
        if to!=fd:f(to)
    
    
f(0)
print(*cnt,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
### BUGGY CODE ###

n=int(input())
list=[]
list1=[]
for i in range(n):
    a,b=map(str,input().split())
    if a=="insert":
        list.append(b)
    if a=="find":
        if b in list:
            list1.append(1)
        else:
            list1.append(0)

for i in range(len(list1)):
    if list1[i]==1:
        print("yes")
    else:
        print("no")
        


### FIXED CODE ###

n=int(input())
list={}
list1=[]
for i in range(n):
    a,b=map(str,input().split())
    if a=="insert":
        list.setdefault(b,i)
    if a=="find":
        if b in list:
            list1.append("yes")
        else:
            list1.append("no")

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

N,K = map(int, input().split())
num = []
num.append(N)

min = N
while True:
    if K == 1:
        print(0)
        break

    N = abs(N - K)
    if  (N in num)  == True:
        print(min)
        break
    else:
        num.append(N)
        if N < min:
            min = N


### FIXED CODE ###

N,K = map(int, input().split())
num = []
num.append(N)

if N > K:
    s = N // K
    N -= (K * s)
min = N
if K == 1:
    print(0)
else:
    while True:
        if K == 1:
            print(0)
            break
        N = abs(N - K)
        if  (N in num)  == True:
            print(min)
            break
        else:
            num.append(N)
            if N < min:
                min = N
### BUGGY CODE ###

N = input()
S = list(map(int, input()[:]))
ans = 0
for num in range(1000):
    n1,n2,n3 = 0, 0, num%10
    n2= (num %100-n3)// 10
    n1 = (num-n2*10- n3) //100
    f1 = False
    f2 = False
    f3 = False
    for n in S:
        if not f1:
            if n == n1:
                f1 = True
        elif not f2:
            if n == n2:
                f2 = True
        elif not f3:
            if n == n3:
                f3 = True
                break
    if f1 and f2 and f3:
        ans += 1
print(ans)


### FIXED CODE ###

import copy

N = input()
S = list(map(int, input()[:]))
left = [False for i in range(10)]
right = [0 for i in range(10)]

for n in S[1:]:
    right[n] += 1
left[S[0]] = True
flag = [[[False for i in range(10)] for j in range(10)] for k in range(10)]
for n in S[1:-1]:
    right[n] -= 1
    for i, l in enumerate(left):
        if l:
            for j, r in enumerate(right):
                if r > 0:
                    flag[n][i][j] = True
    left[n] = True
count = 0
for i in flag:
    for j in i:
        for k in j:
            if k:
                count += 1
print(count)
### BUGGY CODE ###

a=list(map(int,input().split()))
b=list(map(lambda b:abs(int(b)-a[1]),input().split()))
def ucl(a,b):
  if a%b==0:
    return b
  else:
    return ucl(b,a%b)
while len(b)>1:
  b.append(ucl(b[0],b[1]))
  del b[0]
  del b[0]
print(b[0])  

### FIXED CODE ###

a=list(map(int,input().split()))
x=[]
for i in input().split():
  x.append(abs(int(i)-a[1]))
def ucl(a,b):
  if a%b==0:
    return b
  else:
    return ucl(b,a%b)
while len(x) > 1:
  x2 = []
  mn_x = min(x)
  for n in range(len(x)):
    mod = x[n] % mn_x
    if mod != 0:
      x2.append(mod)
  x2.append(mn_x)
  x = x2
print(x[0])
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0

for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    k=j+1
    while k<N and L[k]<a+b:
      k+=1
    ans+=(k-1-j)

print(ans)


### FIXED CODE ###

from bisect import bisect_left

N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0

for i in range(N-2):
  a=L[i]
  for j in range(i+1,N-1):
    b=L[j]
    ans+=bisect_left(L,a+b)-(j+1)
print(ans)
### BUGGY CODE ###

import sys
mod=10**9+7

N,M=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)

for i in range(0,N-1):
  if alist[i]==alist[i+1]:
    print(0)
    sys.exit()
for i in range(0,M-1):
  if blist[i]==blist[i+1]:
    print(0)
    sys.exit()

answer=1
cnt_a=0
cnt_b=0
for i in reversed(range(1,N*M+1)):
  if i in alist and i in blist:
    cnt_a+=1
    cnt_b+=1
  elif i in alist:
    cnt_a+=1
    answer*=cnt_b
    answer%=mod
  elif i in blist:
    cnt_b+=1
    answer*=cnt_a
    answer%=mod
  else:
    answer*=(cnt_a*cnt_b-(N*M-i))
    answer%=mod
    
  if answer==0:
    break
    
print(answer)

### FIXED CODE ###

import sys
mod=10**9+7

N,M=map(int,input().split())
alist=list(map(int,input().split()))
blist=list(map(int,input().split()))

alist.sort(reverse=True)
blist.sort(reverse=True)

for i in range(0,N-1):
  if alist[i]==alist[i+1]:
    print(0)
    sys.exit()
for i in range(0,M-1):
  if blist[i]==blist[i+1]:
    print(0)
    sys.exit()

alist.append(0)
blist.append(0)
    
answer=1
cnt_a=0
cnt_b=0
for i in reversed(range(1,N*M+1)):
  if alist[cnt_a]==i and blist[cnt_b]==i:
    cnt_a+=1
    cnt_b+=1
  elif alist[cnt_a]==i:
    cnt_a+=1
    answer*=cnt_b
    answer%=mod
  elif blist[cnt_b]==i:
    cnt_b+=1
    answer*=cnt_a
    answer%=mod
  else:
    answer*=(cnt_a*cnt_b-(N*M-i))
    answer%=mod
    
  if answer==0:
    break
    
print(answer)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a1 = set(a)
default = 0
for i in a1:
    default += a.count(i) * (a.count(i) - 1) // 2
for k in a:
    print(default - (a.count(k) - 1))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
cnt = 0
for i in c.values():
    cnt += i * (i - 1) // 2
for i in a:
    print(cnt - c[i] + 1)
### BUGGY CODE ###

S=list(input())
N=len(S)
dp=[[0]*13 for i in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(1,N+1):
  for j in range(13):
    if dp[i-1][j]>0:
      if S[i-1]=="?":
        for k in range(10):
          dp[i][(j*10+k)%13]+=dp[i-1][j]
      else:
        
        dp[i][(j*10+int(S[i-1]))%13]+=dp[i-1][j]
print(dp[N][5]%mod)


        


### FIXED CODE ###

S=list(input())
N=len(S)
dp=[[0]*13 for i in range(N+1)]
dp[0][0]=1
mod=10**9+7
for i in range(1,N+1):
  for j in range(13):
    if dp[i-1][j]>0:
      if S[i-1]=="?":
        for k in range(10):
          dp[i][(j*10+k)%13]+=dp[i-1][j]
          dp[i][(j*10+k)%13]%=mod
      else:
        dp[i][(j*10+int(S[i-1]))%13]+=dp[i-1][j]
        dp[i][(j*10+int(S[i-1]))%13]%=mod
print(dp[N][5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 入力を変数に格納
count = int(input())
num_list = [int(i) for i in input().split()]

result = 0
for i in range(count):
    # 合計初期化
    num_sum = 0
    # 開始位置を一つずつ前にずらす
    for j in range(i, count):
        num_sum += num_list[j]
        # 前から順番に足していって0になるやつを探す
        if num_sum == 0:
            result += 1

print(result)

### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/agc023/editorial.pdf
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, initial=1)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    return factorial(n) // (factorial(r) * factorial(n-r))

N = INT()
aN = LIST()

sm = [0] * (N+1)
for i in range(N):
    sm[i+1] = sm[i] + aN[i]

c = Counter(sm)
ans = 0
for k, v in c.items():
    if v >= 2:
        ans += nCr(v, 2)
print(ans)
### BUGGY CODE ###

import itertools


def d():
    _ = int(input())
    ls = list(map(int, input().split()))
    combs = list(itertools.combinations(ls, 3))
    count = 0
    a = 0
    b = 1
    c = 2

    for comb in combs:
        if comb[a] < comb[b] + comb[c] and comb[b] < comb[c] + comb[a] and comb[c] < comb[a] + comb[b]:
            count += 1
    print(count)


if __name__ == '__main__':
    d()


### FIXED CODE ###

def d():
    n = int(input())
    ls = list(map(int, input().split()))
    ls.sort()
    count = 0
    for i in range(n-1):
        k = i + 2
        for j in range(i+1, n-1):
            while k < n and ls[i] + ls[j] > ls[k]:
                k += 1
            count += k - j - 1

    print(count)


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

S = input()

n = len(S)

modlist = [0] * 2019
num = 0

for i in range(n):
    fig = int(S[n - i - 1])
    num += fig * (10 ** i)
    modlist[num % 2019] = modlist[num % 2019] + 1

result = 0
if modlist[0] > 0:
    result += 1

for i in range(2019):
    if modlist[i] != 0:
        result += modlist[i] * (modlist[i] - 1) / 2

print(int(result))

### FIXED CODE ###

S = input()

n = len(S)

medalist = [0] * 2019
medalist[0] = 1
num = 0
mods = 1

for i in range(n):
    fig = int(S[n - i - 1])
    num = (num + fig * mods) % 2019
    medalist[num] = medalist[num] + 1
    mods = (mods * 10) % 2019

result = 0

for i in range(2019):
    m = medalist[i]
    if m != 0:
        result += m * (m - 1) / 2

print(int(result))
### BUGGY CODE ###

N = int(input())
R = []
for i in range(N):
    R.append(int(input()))

mprof = R[1] - R[0]
for i in range(1, len(R)):
    for k in range(i):
        if mprof < (R[i] - R[k]):
            mprof = (R[i] - R[k])

print(mprof)

### FIXED CODE ###

N = int(input())
R = []
for i in range(N):
    R.append(int(input()))

maxv = R[1] - R[0]
minv = R[0]
for i in range(1, len(R)):
        maxv = max(maxv, (R[i] - minv))
        minv = min(minv, R[i])

print(maxv)
### BUGGY CODE ###

import math

Num,HP = (map(int,input().split()))
Katanas = [list(map(int,input().split())) for x in range(Num)]

amax = max([x[0] for x in Katanas])
bpower = sorted([x[1] for x in Katanas if x[1] > amax],reverse=True)
attake=0
if len(bpower):
    while HP > 0:
        attake += 1
        HP -= bpower[0]
        if len(bpower) == 1:
            break
        bpower = bpower[1:]
attake += math.ceil(HP/amax) if HP > 0 else 0
print(attake)

### FIXED CODE ###

import math

Num,HP = (map(int,input().split()))
#Katanas = [list(map(int,input().split())) for _ in range(Num)]

CKatanaMax = 0
katanas = []

for _ in range(Num):
    a,b = map(int,input().split())
    CKatanaMax = max(CKatanaMax,a)
    katanas.append(b)

Tkatanas = sorted([x for x in katanas if x > CKatanaMax],reverse=True)

attake = 0
for Tkatana in Tkatanas:
    HP -= Tkatana
    attake += 1
    if HP <= 0:
        break
else:
    attake += math.ceil(HP/CKatanaMax)
print(attake)
### BUGGY CODE ###

import sys
import numpy as np

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1))
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    for col in range(1,W+1):
        if w[row] <= col:
            dp[row+1,col] = max(v[row]+dp[row,col-w[row]],dp[row,col])
        else:
            dp[row+1,col] = dp[row,col]

ans = int(max(dp[N]))
print(ans)

### FIXED CODE ###

import sys
import numpy as np


input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])
print(dp[N,-1])
### BUGGY CODE ###

n=int(input())
a=0
for i in range(1,n):
    a+=i
print(a)

### FIXED CODE ###

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

N = int(input())
p = 1
for i in range(1,N+1):
    p *= i
print(p%(10**9+7))

### FIXED CODE ###

from math import factorial
N = int(input())
print(factorial(N)%(10**9+7))
### BUGGY CODE ###

import collections
n, k = map(int, input().split())
list = input().split()
c_list = collections.Counter(list)
sorted_c_list = sorted(c_list.values())
for i in range(len(sorted_c_list)):
  if len(sorted_c_list[i:])==k:
    print(sum(sorted_c_list[:i]))
    break
else:
  print(0)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
list = input().split()
c_list = collections.Counter(list)
sorted_c_list = sorted(c_list.values(),reverse=True)
print(sum(sorted_c_list[k:]))
### BUGGY CODE ###

n, q = (int(_) for _ in input().split())  
arr = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
output = [0 for i in range(n)]

for i in range(n-1):
  a, b = (int(_) for _ in input().split()) 
  arr[a-1][b-1] = 1
  for x in range(a-1):
    if arr[x][a-1] == 1:
      arr[x][b-1] = 1

for i in range(q):
  p, q = (int(_) for _ in input().split()) 
  for i, x in enumerate(arr[p-1]):
    if x == 1:
      output[i] += q
    
print(' '.join([str(x) for x in output]))

### FIXED CODE ###

n,q=map(int,input().split())
a=[0]*(n-1)
c=[0 for i in range(n)]
for i in range(n-1):
  a[i]=list(map(int,input().split()))

a.sort()

for i in range(q):
  x,y=map(int,input().split())
  c[x-1]+=y

for i in range(n-1):
  c[a[i][1]-1]+=c[a[i][0]-1]

print(*c)
### BUGGY CODE ###

#155
def main():
    N = int(input())
    S = [input() for i in range(N)]
    S_set = set(S)
    max_num = 0
    candidate = []
    for s in S_set:
        if S.count(s) == max_num: 
            candidate.append(s)
        elif S.count(s) > max_num:
            max_num = S.count(s)
            candidate=[s]
    candidate.sort()
    for c in candidate:
        print(c)
main()

### FIXED CODE ###

#155
def main():
    N = int(input())
    S = [input() for i in range(N)]
    S.sort()
    ans = []
    max_len = 0
    streak = 1
    for i in range(N-1):
        if(S[i]==S[i+1]):
            streak+=1
            if(i==N-2):
                if(streak>max_len):
                    max_len = streak
                    ans = [S[i]]
                elif(streak==max_len):
                    ans.append(S[i])
        else:
            if(streak>max_len):
                max_len = streak
                ans = [S[i]]
            elif(streak==max_len):
                ans.append(S[i])
            streak=1
    if(N==1 or S[-2]!=S[-1]):
        ans.append(S[-1])
    for a in ans:
        print(a)
main()
### BUGGY CODE ###

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

count = 0
num = range(k+1)
for x in num:
  for y in num:
    if x + y > s:
      break
    for z in num:
      if x + y + z == s:
        count += 1
      elif x + y + z > s:
        break

print(count)

### FIXED CODE ###

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

count = 0
for x in range(k+1):
  for y in range(k+1):
    a = s - x - y
    if a >= 0 and a <= k:
      count += 1

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

n = int(input())
data = list(map(int, input().split()))
 
a = 1
i = 0
while i<n:
  if data[i]==0:
    a = 0
    break
  a = a*data[i]
  i += 1

if a > 10**18:
  a = -1
 
print(a)

### FIXED CODE ###

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

flag = 0
if data.count(0) > 0:
	print(0)
else:
  a = data[0]
  for i in range(1,n):
    a = a*data[i]
    if a > 10**18:
      flag = 1
      break
      
  if flag == 1:
    print('-1')
  else:
    print(a)
### BUGGY CODE ###

H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  row = list(input())
  blocks += row.count("#")
  matrix.append(row)

q = [(0,0,0)]
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]

while q:
  r,c,step = q.pop(0)
  # visited.append((r,c))
  visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc]: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )


### FIXED CODE ###

import sys
readline = sys.stdin.readline
from collections import deque
H,W = list(map(int, input().split()))
matrix = []
blocks = 0
for _ in range(H):
  # row = list(input())
  row = readline().rstrip()
  blocks += row.count("#")
  matrix.append(row)

q = deque([(0,0,0)])
min_step = -1
# visited = []
visited = [ [False]*W for _ in range(H) ]
visited[0][0] = True

while q:
  r,c,step = q.popleft()
  # visited.append((r,c))
  # visited[r][c] = True

  for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
    nr,nc = r+i,c+j
    if nr==H-1 and nc==W-1: 
      min_step = step+1
      q = []
      break

    if nr<0 or nc<0 or nr>=H or nc>=W: continue
    if visited[nr][nc] or (nr,nc,step+1) in q: continue
    # if (nr,nc) in visited: continue
    if matrix[nr][nc] == "#": continue
    visited[r][c] = True
    q.append((nr,nc,step+1))

if min_step == -1:
  print(-1)
else:
  print( H*W - blocks - min_step -1 )
### BUGGY CODE ###


k=int(input())

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

res=0

for n in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):
            res+=gcd(n, i,j)

print(res)





### FIXED CODE ###

k=int(input())

from math import gcd
 
res=0
 
for n in range(1,k+1):
    for i in range(1,k+1):
        for j in range(1,k+1):

            res+=gcd(gcd(n,i),j)

print(res)
### BUGGY CODE ###

n= int(input())
a=list(map(int,input().split()))
ans = 1
for i in range(n):
  ans*=a[i]
if ans>1e+18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n= int(input())
a=list(map(int,input().split()))
ans = 1
if not 0 in a:
  for i in range(n):
    ans*=a[i]
    if ans>1e+18:
      print(-1)
      break     
  if ans<=1e+18:
    print(ans)
else:
  print(0)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
l = 0
r = k - 1
ans_max = 0
for i in range(n-k+1):
    ans = 0
    for j in range(l, r+1):
        ans += (p[j]+1) / 2
    ans_max = max(ans, ans_max)
    l += 1
    r += 1

print(ans_max)

### FIXED CODE ###

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

kitaiti = [0 for _ in range(n)]
ruisekiwa = [0 for _ in range(n)]
r = k - 1
max = 0
now = 0
ans_list = []

for i in range(n):
    kitaiti[i] = (p[i]+1) / 2
    if i == 0:
        ruisekiwa[0] = kitaiti[0]
    else:
        ruisekiwa[i] = ruisekiwa[i-1] + kitaiti[i]
    if i == r:
        now = ruisekiwa[i]
    elif i > r:
        now = ruisekiwa[i] - ruisekiwa[i-r-1]
    if now > max:
        max = now
print(max)
### BUGGY CODE ###

il1 = [int(k) for k in input().split()]
N = il1[0]
M = il1[1]
answered = []
result = [0, 0]
was = [0]
was = was * (N+1)

for i in range(M):
    il = input().split()
    p = int(il[0])
    s = il[1]
    if (p in answered):
        pass
    else:
        if (s == 'AC'):
            result[0] = result[0]+1
            answered.append(p)
            result[1] = result[1]+was[p]
        else:
            was[p] = was[p] + 1

print(str(result[0])+" "+str(result[1]))


### FIXED CODE ###

il1 = [int(k) for k in input().split()]
N = il1[0]
M = il1[1]
answered = ['WA']
answered = answered * (N+1)
result = [0, 0]
was = [0]
was = was * (N+1)

for i in range(M):
    il = input().split()
    p = int(il[0])
    s = il[1]
    if (answered[p] == 'AC'):
        pass
    else:
        if (s == 'AC'):
            result[0] = result[0]+1
            answered[p] = s
            result[1] = result[1]+was[p]
        else:
            was[p] = was[p] + 1

print(str(result[0])+" "+str(result[1]))
### BUGGY CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    *z,=zip(sorted(a[:n]),sorted(a[n:],reverse=1))
    ok=10**12
    ng=-1
    while ok-ng>1:
        mid=(ok+ng)//2
        l=k
        for b,g in z:
            if b*g>mid:l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    a,f=sorted(a[:n])[::-1],sorted(a[n:])
    ok=10**12
    ng=-1
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        l=k
        for b,g in zip(a,f):
            if b*g>mid:
                l-=b-mid//g
        if l<0:ng=mid
        else:ok=mid
    print(ok)
main()
### BUGGY CODE ###

s = input()
q = int(input())
rev = False
for _ in range(q):
    query = input()
    if query == "1":
        rev = not rev
    else:
        _, f, c = query.split(" ")
        if f == "1":
            if rev:
                s = s + c
            else:
                s = c + s
        else:
            if rev:
                s = c + s
            else:
                s = s + c

if rev:
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
rev = False
L = ""
R = ""
for _ in range(q):
    query = input()
    if query == "1":
        rev = not rev
    else:
        _, f, c = query.split(" ")
        if f == "1":
            if rev:
                R = R + c
            else:
                L = c + L
        else:
            if rev:
                L = c + L
            else:
                R = R + c

if rev:
    s = s[::-1]
    L = L[::-1]
    R = R[::-1]
    print(R + s + L)
else:
    print(L + s + R)
### BUGGY CODE ###

import math

a, b, n = [int(x) for x in input().split()]

m = 0
for i in range(1, n + 1):
    m = max(m, math.floor(a * i / b) - a * math.floor(i / b))

print(m)

### FIXED CODE ###

import math

a, b, n = [int(x) for x in input().split()]
# a = 10 ** 6
# b = 10 ** 12
# n = 10 ** 12

m = 0
if (n < b):
    # math.floor(x / b) = 0
    m = math.floor(a * n / b) # - a * math.floor(n / b)
else:
    m = math.floor(a * (b - 1) / b) - a * math.floor((b - 1) / b)
    #for i in range(n // b - 1, n + 1, b):
    # for i in range(n):
    #     print(i, math.floor(a * i / b),  a * math.floor(i / b), math.floor(a * i / b) - a * math.floor(i / b))
    #     m = max(m, math.floor(a * i / b) - a * math.floor(i / b))

print(m)
### BUGGY CODE ###

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]

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

solver()

### FIXED CODE ###

def solver():
	N,W = map(int, input().split())
	item = []
	for i in range(N):
		item.append(list(map(int, input().split())))
	dp = [0 for _ in range(W+1)]
 
	for i in range(0,N):
		for j in range(W, item[i][0]-1, -1):
			dp[j] = max(dp[j], dp[j-item[i][0]]+item[i][1])
	print(dp[W])
 
solver()