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

N = int(input())
ans = []
for i in range(N):
    A = input()
    if A in ans:
        ans.remove(A)
    else:
        ans.append(A)
print(len(ans))

### FIXED CODE ###

N = int(input())
ans = {}
for i in range(N):
    A = input()
    if  A in ans:
        ans[A] += 1
    else:
        ans[A] = 1
c = 0
for i in ans:
    if ans[i] % 2 == 1:
        c += 1
print(c)
### BUGGY CODE ###

from sys import stdin


def b(input_string):
    _s = input_string
    s_length = len(_s)
    s = []
    for i in range(s_length):
        s.append(_s[i])
    #print(_s)
    #print(s)
    count = 0
    flag = True
    while flag and len(s) >= 2:
        flag = False
        for i in range(s_length):
            if i < len(s)-1:
                if s[i] != s[i+1]:
                    s.pop(i)
                    #print(s)
                    s.pop(i)
                    #print(s)
                    count += 2
                    flag = True
                    break
    return count



def main():
    input_line = stdin.readline().rstrip()
    answer = b(input_line)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin


def b(input_string):
    _s = input_string
    s_length = len(_s)
    s = []
    for i in range(s_length):
        s.append(_s[i])
    count = 0
    i = 0
    while(i < len(s)-1):
        #print(s)
        #print(i)
        if s[i] != s[i+1]:
            s.pop(i)
            s.pop(i)
            count += 2
            if i != 0:
                i -= 1
        else:
            i += 1
    return count



def main():
    input_line = stdin.readline().rstrip()
    answer = b(input_line)
    print(answer)


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

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

count = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i+j+k == s:
                count += 1

print(count)    

### FIXED CODE ###

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

count = 0
for i in range(n+1):
    for j in range(n+1):
        if s-i-j <= n and s-i-j >= 0:
            count += 1


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

from sys import stdin
n = int(stdin.readline().rstrip())
point = 0
for i in range(1,n+1):
    if n%i == n//i:
        point += i
print(point)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
li = make_divisors(n)
point = 0
for i in li:
    minashi = i-1
    if minashi == 0:
        continue
    elif n%minashi == n//minashi:
        point += minashi
print(point)
### BUGGY CODE ###

n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

amax = 0
count = 0

for i in alst:
    if alst[amax] + count <= k:
        count += alst[amax]
        amax += 1
    else:
        break
# print("a:" + str(amax))
"""
while alst[amax] + count <= k:
    # print(str(amax) + " " + str(count))
    count += alst[amax]
    amax += 1
# print(amax)
#amaxはaの最大冊数
"""

anslst = []
count = 0
for i in range(amax+1):
    count = sum(alst[:i])
    bmax = 0
    for j in blst:
        if blst[bmax] + count <= k:
            count += blst[bmax]
            bmax += 1
        else:
            break
    # print("i:" + str(i) + " b:" + str(bmax))
    anslst.append(i+bmax)

print(max(anslst))


### FIXED CODE ###

n, m, k = map(int, input().split())
alst = list(map(int, input().split()))
blst = list(map(int, input().split()))

asum = [0]
bsum = [0]

for i, new in enumerate(alst):
    if asum[i] + new <= k:
        asum.append(asum[i] + new)
    else:
        break
for i, new in enumerate(blst):
    if bsum[i] + new <= k:
        bsum.append(bsum[i] + new)
    else:
        break

bmax = len(bsum)-1
ans = 0

for i, atime in enumerate(asum):
    while atime + bsum[bmax] > k:
        bmax -= 1
    ans = max(ans, i+bmax)

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

n = int(input())
s = input()
ans = n
for i in range(n):
    e = s[:i]
    w = s[i + 1:]
    ans = min(ans,e.count('W') + w.count('E'))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = [s[1:n].count("E")]
for i in range(1, n):
    #ans.append(s[:i].count('W') + s[i+1:].count('E'))
    ans.append(ans[i-1]-int(s[i] is "E")+int(s[i-1] is "W"))
print(min(ans))
### BUGGY CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for n in range(2,N):
  for k in range(1,n):
    for l in range(k):
      if L[n]<L[k]+L[l]:
        ans+=1
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L.sort()
ans=0
for n in range(1,N):
  b=L[n]
  for k in range(n):
    a=L[k]
    index=bisect.bisect_left(L,a+b)
    ans+=(index-n-1)
print(ans)
### BUGGY CODE ###

import sys
s = sys.stdin.readlines()

N,Q = map(int, s[0].split())
L = []
for i in s[1:N+1]:
    t = list(map(int, i.split()))
    L.append(t)
D = []
for i in s[N+1:]:
    D.append(int(i))

import heapq

List = []
for i in range(N):
    List.append([L[i][0]-0.5-L[i][2], 1, L[i][2]])
    List.append([L[i][1]-0.5-L[i][2], -1, L[i][2]])
    
List.sort()

h_in = []
h_ex = []
ans = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h_in, List[j][2])
        else:
            heapq.heappush(h_ex, List[j][2])
        j += 1
    while len(h_in) > 0 and len(h_ex) > 0 and h_in[0] == h_ex[0]:
        heapq.heappop(h_in)
        heapq.heappop(h_ex)
    if h_in:
        ans.append(h_in[0])
    else:
        ans.append(-1)
    
for i in range(Q):
    print(ans[i])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N,Q = map(int, input().split())
List = []
dic = {}
for _ in range(N):
    s, t, x = map(int, input().split())
    List.append((s-0.5-x, 1, x))
    List.append((t-0.5-x, -1, x))
    dic[x] = False

import heapq
    
List.sort()

h = []
j = 0
for _ in range(Q):
    D = int(input())
    while j < 2*N and List[j][0] < D:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)
### BUGGY CODE ###

from collections import Counter
from math import factorial


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return factorial(n) // (2 * factorial(n - 2))


N = int(input())
A = list(map(int, input().split()))
for k in range(N):
    c = Counter(A[:k] + A[k + 1:])

    print(sum(map(choose, c.values())))


### FIXED CODE ###

from collections import Counter


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return (n * (n - 1)) // 2


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
d = {key: choose(value) for key, value in c.items()}
if len(d) > 1:
    sum_d = sum(d.values())
    for a in A:
        print(sum_d - d[a] + choose(c[a] - 1))
else:
    ans = choose(N - 1)
    for _ in range(N):
        print(ans)
### BUGGY CODE ###

N, M, L = map(int, input().split())
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
for k in range(N):
    for i in range(N):
        for j in range(N):
            G[i][j] = min(G[i][j], G[i][k] + G[k][j])


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
for k in range(N):
    for i in range(N):
        for j in range(N):
            E[i][j] = min(E[i][j], E[i][k] + E[k][j])


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, input().split())
    s, t = s - 1, t - 1
    print(E[s][t] - 1 if E[s][t] != float('inf') else - 1)


### FIXED CODE ###

import sys
from scipy.sparse.csgraph import floyd_warshall
N, M, L = map(int, input().split())
INF = 10 ** 9 + 1
G = [[float('inf')] * N for i in range(N)]
for i in range(M):
    a, b, c = map(int, sys.stdin.readline().split())
    a, b = a - 1, b - 1
    G[a][b] = c
    G[b][a] = c


# 全点間最短距離を計算
G = floyd_warshall(G)


# コストL以下で移動可能な頂点間にコスト１の辺を張る
E = [[float('inf')] * N for i in range(N)]
for i in range(N):
    for j in range(N):
        if G[i][j] <= L:
            E[i][j] = 1


# そのグラフの全点間最短距離を求める
E = floyd_warshall(E)


# クエリに答えていく
Q = int(input())
for i in range(Q):
    s, t = map(int, sys.stdin.readline().split())
    s, t = s - 1, t - 1
    print(int(E[s][t] - 1) if E[s][t] != float('inf') else - 1)
### BUGGY CODE ###

n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)


### FIXED CODE ###

n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)
### BUGGY CODE ###

temp = list(map(int, input().split()))
N = temp[0]
K = temp[1]
Q = temp[2]
A = []
p = []
for i in range(N):
  p.append(K)
for i in range(Q):
  A.append(int(input())-1)
  for j in range(N):
    if(j != A[i]):
      p[j] -= 1
      
for i in range(N):
  if(p[i]>0):
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

temp = list(map(int, input().split()))
N = temp[0]
K = temp[1]
Q = temp[2]
A = []
anscount = []
for i in range(N):
  anscount.append(0)
for i in range(Q):
  A.append(int(input())-1)
  anscount[A[i]] += 1
      
for i in range(N):
  if(K - Q + anscount[i] >0):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)
    def add(self,x,w):
        while x <= self.n:
            self.bit[x] += w
            x += (x&-x)
            
    def sum(self,x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= (x&-x)
        return cnt

    def psum(self,a,b):
        return self.sum(b-1)-self.sum(a-1)

    def bisect(self, w):
        # 値がw以上となる最小のindex
        x = 0
        k = 1
        while k < self.n:
            k *= 2            
        while k > 0:
            # x+kの値がwより小さければ、treeの右側に移動
            if x+k<=self.n and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k            
            k //= 2
        return x + 1
    
n = int(input())
ps = list(map(int, input().split()))

# 1-indexedにする
inds = [0]*(n+1)
for i, p in enumerate(ps):
    inds[p] = i+1
bit = BIT(n)
cnt = 0
# 大きい順に
for p in range(n,0,-1):
    ind = inds[p]
    nl = bit.sum(ind)   # 自分より左にあるやつの個数
    nr = (n-p) - nl     # 自分より左にあるやつの個数    
    bit.add(ind, 1)     # bitを1で埋めていく
    # 自分を含んで左右のインデックスを見る(端注意)
    ixl2 = bit.bisect(nl-1) if nl >= 2 else 0
    ixl1 = bit.bisect(nl)   if nl >= 1 else 0
    ixr1 = bit.bisect(nl+2) if nr >= 1 else n+1
    ixr2 = bit.bisect(nl+3) if nr >= 2 else n+1
    tmp = 0
    tmp += (ixl1-ixl2)*(ixr1-ind) #左側から1個取る
    tmp += (ixr2-ixr1)*(ind-ixl1) #右側から1個取る
    cnt += p*tmp    
    # print("p",p,nl,nr,"ind",ixl2,ixl1,ind,ixr1,ixr2,tmp,cnt)
print(cnt)

### FIXED CODE ###

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)
    def add(self,x,w):
        while x <= self.n:
            self.bit[x] += w
            x += (x&-x)
            
    def sum(self,x):
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            x -= (x&-x)
        return cnt

    def psum(self,a,b):
        return self.sum(b-1)-self.sum(a-1)

    def bisect(self, w):
        # 値がw以上となる最小のindex
        x = 0
        k = 1
        while k < self.n:
            k *= 2            
        while k > 0:
            # x+kの値がwより小さければ、treeの右側に移動
            if x+k<=self.n and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k            
            k //= 2
        return x + 1
    
n = int(input())
ps = list(map(int, input().split()))

# 1-indexedにする
inds = [0]*(n+1)
for i, p in enumerate(ps):
    inds[p] = i+1
bit = BIT(n)
cnt = 0
# 大きい順に
for p in range(n,0,-1):
    ind = inds[p]
    nl = bit.sum(ind)   # 自分より左にあるやつの個数
    nr = (n-p) - nl     # 自分より左にあるやつの個数    
    bit.add(ind, 1)     # bitを1で埋めていく
    # 自分を含んで左右のインデックスを見る(端注意)
    ixl2 = bit.bisect(nl-1) if nl >= 2 else 0
    ixl1 = bit.bisect(nl)   if nl >= 1 else 0
    ixr1 = bit.bisect(nl+2) if nr >= 1 else n+1
    ixr2 = bit.bisect(nl+3) if nr >= 2 else n+1
    tmp = 0
    tmp += (ixl1-ixl2)*(ixr1-ind) #左側から1個取る
    tmp += (ixr2-ixr1)*(ind-ixl1) #右側から1個取る
    cnt += p*tmp    
    # print("p",p,nl,nr,"ind",ixl2,ixl1,ind,ixr1,ixr2,tmp,cnt)
print(cnt)
### BUGGY CODE ###

# encoding: utf-8


import sys

__input = sys.stdin.readlines()
length_1 = int(__input[0])
array_1 = list(map(int, __input[1].split()))
length_2 = int(__input[2])
array_2 = list(map(int, __input[3].split()))


def solution():
    # print(length_1, array_1, length_2, array_2)
    assert length_1 == len(array_1) and length_2 == len(array_2)

    for i in range(length_2):
        ans = solve(0, array_2[i])
        if ans:
            print("yes")
        else:
            print("no")
    return None


def solve(i, m):
    if m == 0:
        return True
    if i >= length_1:
        return False
    res = solve(i + 1, m) or solve(i + 1, m - array_1[i])
    return res


if __name__ == '__main__':
    solution()

### FIXED CODE ###

# encoding: utf-8


import sys

__input = sys.stdin.readlines()
length_1 = int(__input[0])
array_1 = list(map(int, __input[1].split()))
length_2 = int(__input[2])
array_2 = list(map(int, __input[3].split()))

record = [False] * 2000


def solution():
    # print(length_1, array_1, length_2, array_2)
    assert length_1 == len(array_1) and length_2 == len(array_2)

    for i in array_1:
        # record[i] = True
        for j in range(2000 - i, 0, -1):
            if record[j]:
                # print(j, i + j)
                record[i + j] = True
        record[i] = True

    for index in array_2:
        if record[index]:
            print("yes")
        else:
            print("no")


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

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

ct=1
for i in range(N-1):
	for j in range(i+1):
		if P[i-j]<=P[i+1]:
			break
		elif j==i:
			ct+=1
			
  
    

print(ct)

### FIXED CODE ###

import numpy as np
N=int(input())
P=list(map(int,input().split()))

ct=0
min_p=P[0]
for i in range(N):
	if P[i]<=min_p:
		min_p=P[i]
		ct+=1


print(ct)
### BUGGY CODE ###

import numpy as np
H, W, K = map(int, input().split())
S = []
inf = 100000
ans = inf
for i in range(H):
    S.append([int(x) for x in input()])
S = np.array(S)
for i in range(2**(H-1)):
    hlis = [0]
    for j in range(H-1):
        if ((i>>j) & 1):
            hlis.append(j+1)
    hlis.append(H)
    hlis = np.array(hlis)
    wkireme = 0
    numwkireme = 0
    Flag1 = True
    Flag2 = True
    w = 1
    while Flag1:
        for n in range(len(hlis)-1):
            s = np.sum(S[hlis[n]:hlis[n+1],wkireme:wkireme+w])
            if s > K:
                if w == 1:
                    Flag2 = False
                    Flag1 = False
                    break
                else:
                    wkireme = wkireme + w -1
                    numwkireme += 1
                    w = 1
                    break
        else:
            if wkireme + w >= W:
                Flag1 = False
            else:
                w += 1
    if Flag2:
        ans = min(ans, numwkireme + len(hlis) -2)
print(ans)


### FIXED CODE ###

def main():
    import sys
    inf = 100100100
    ans = inf
    H, W, K = map(int, input().split())
    S = [0]*H
    for i in range(H):
        S[i] = [int(x) for x in sys.stdin.readline().strip()]
    for i in range(2**(H-1)):
        group = [0]
        g = 0
        for j in range(H-1):
            if (i >> j) & 1:
                g += 1
            group.append(g)
        g += 1
        c = [[0 for _ in range(W)] for __ in range(g)]
        for j in range(H):
            for k in range(W):
                c[group[j]][k] += S[j][k]
        num = g-1
        now = [0]*g
        def large(now):
            for n in now:
                if n > K:
                    return True
            else:
                return False
        def v_vec(twodlis, k):
            ans = []
            for lis in twodlis:
                ans.append(lis[k])
            return ans
        for k in range(W):
            for n in range(len(now)):
                now[n] = now[n] + v_vec(c,k)[n]
            if large(now):
                now = v_vec(c,k)
                num += 1
                if large(now):
                    num = inf
                    break

        ans = min(ans, num)
    print(ans)

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

INF = 10000
n,k = map(int,input().split())
stair = list(map(int,input().split()))
dp = [0] *n
for i in range(1,n):
    dp[i] = dp[i-1]+abs(stair[i]-stair[i-1])
    for j in range(1,k+1):
        if(i - j >= 0):
            # print(i,i-j)
            dp[i] = min(dp[i], dp[i-j]+abs(stair[i]-stair[i-j]))
        # print(dp)



print(dp[-1])

### FIXED CODE ###

INF = 10000
n,k = map(int,input().split())
stair = list(map(int,input().split()))
dp = [0] *n
for i in range(1,n):
    dp[i] = dp[i-1]+abs(stair[i]-stair[i-1])
    for j in range(1,k+1):
        if(i - j >= 0):
            # print(i,i-j)
            dp[i] = min(dp[i], dp[i-j]+abs(stair[i]-stair[i-j]))
        # print(dp)



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

N=int(input())
A=list(map(int,input().split()))
ans=1
for a in A:
    ans=ans*a
if ans > 10**18:
    ans = -1
print(ans)

### FIXED CODE ###

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

n, m = map(int, input().split())
solved = []
wa_history = {}

for i in range(m):
    t1, t2 = input().split()
    if t1 in solved:
        pass
    elif t2 == 'WA':
        if t1 in wa_history:
            wa_history[t1] += 1
        else:
            wa_history[t1] = 1
    else: # t2 == AC
        solved.append(t1)

wa = 0
for key, value in wa_history.items():
    if key in solved:
        wa += value

print(len(solved), wa)

### FIXED CODE ###

n, m = map(int, input().split())
ss = []

for i in range(m):
    t1, t2 = input().split()
    ss.append([t1, t2])

ss.sort(key=lambda x:x[0])

t = ''
ac = 0
wa = 0
awa = 0
cIsSolved = False
for s in ss:
    if s[0] != t:
        t = s[0]
        cIsSolved = False
        wa = 0
    if s[1] == 'AC' and not cIsSolved:
        cIsSolved = True
        ac += 1
        awa += wa
    if s[1] == 'WA' and not cIsSolved:
        wa += 1
print(ac, awa)
### BUGGY CODE ###

import copy
import statistics

n=int(input())
x=list(map(int,input().split()))
y=copy.copy(x)
s=0
for i in range(n):
    s=x[i]
    y.remove(s)
    print(statistics.median(y))
    y.append(s)


### FIXED CODE ###

import statistics
n=int(input())
x=list(map(int,input().split()))
y=statistics.median(x)
xs=sorted(x)
for i in x:
    if i<y:
        print(xs[n//2])
    else:
        print(xs[n//2-1])
### BUGGY CODE ###

n = int(input())
mov = []
for i in range(5):
    mov.append(int(input()))
mov.reverse()

status = [0 for i in range(6)]
status[0] = n
status.reverse()

# print(mov)
# print(status)

count = 0
while True:
    count += 1
    for i in range(1,len(status)):
        status[i-1] += min(status[i],mov[i-1])
        status[i] -= min(status[i],mov[i-1])
    if status[0]==n:
        print(count)
        exit()
    elif status[-1]==0:
        status.pop(-1)
        mov.pop(-1)


### FIXED CODE ###

import math

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

print(math.ceil(n/min(mov))+4)
### BUGGY CODE ###

def knapsack(val,wt,n,k):
    b = [[0 for _ in range(k+1)]for _ in range(n+1)]
    for i in range(n+1):
        for j in range(k+1):
            if j==0 or i==0:
                b[i][j] = 0
            elif wt[i-1]<=j:
                b[i][j] = max(val[i-1]+b[i-1][j-wt[i-1]],b[i-1][j])
            else:
                b[i][j] = b[i-1][j]
    return b[n][k]
from sys import stdin
input = stdin.readline
n,k = list(map(int,input().split()))
val,wt = [],[]
for _ in range(n):
    x,y = list(map(int,input().split()))
    val.append(y)
    wt.append(x)
p = knapsack(val,wt,n,k)
print(p)

### FIXED CODE ###

def knapsack(val,wt,n,k):
    b = [[0 for _ in range(k+1)]for _ in range(n+1)]
    for i in range(n+1):
        for j in range(k+1):
            if j==0 or i==0:
                b[i][j] = 0
            elif wt[i-1]<=j:
                b[i][j] = max(val[i-1]+b[i-1][j-wt[i-1]],b[i-1][j])
            else:
                b[i][j] = b[i-1][j]
    return b[n][k]
from sys import stdin
input = stdin.readline
n,k = list(map(int,input().split()))
val,wt = [],[]
for _ in range(n):
    x,y = list(map(int,input().split()))
    val.append(y)
    wt.append(x)
p = knapsack(val,wt,n,k)
print(p)
### BUGGY CODE ###

import collections
N = int(input())
B = list(map(int, input().split()))


for i, b in enumerate(B, start=1):
  if b > i:
    print(-1)
    exit()


bnn = collections.defaultdict(
  lambda: collections.defaultdict(dict)
)
def inv_sousa(B, N, now=tuple()):
  if N == 0:
    yield now
  else:
    if now in bnn[B][N] or max(B) > N:
      return
    bnn[B][N][now] = False

    for i in set(B):
      idx = i - 1
      if B[idx] == i:
        yield from inv_sousa(B[:idx] + B[i:], N - 1, now=now + (B[idx],))


for x in inv_sousa(tuple(B), N):
  if x:
    for i in x[::-1]:
      print(i)
    break
else:
  print(-1)

### FIXED CODE ###

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


inv_output = list()
for i in range(N, 0, -1):
  for j in range(i, 0, -1):
    if B[j - 1] == j:
      inv_output.append(B.pop(j - 1))
      break
  else:
    print(-1)
    break
else:
  for i in inv_output[::-1]:
    print(i)
### BUGGY CODE ###

from collections import deque
def score(x):
    cur = x
    p = 0
    while cur>0:
        p += T[cur][2]
        cur = T[cur][0]
    return p
N,Q = map(int,input().split())
G = {}
for _ in range(N-1):
    a,b = map(int,input().split())
    if a not in G:
        G[a] = []
    G[a].append(b)
    if b not in G:
        G[b] = []
    G[b].append(a)
T = {i:[0,[],0] for i in range(1,N+1)}
cur = 1
T[cur][1] = G[cur]
T[cur][0] = -1
hist = deque([cur])
while hist:
    cur = hist.popleft()
    for y in T[cur][1]:
        T[y][0] = cur
        G[y].remove(cur)
        T[y][1] = G[y]
        hist.append(y)
for _ in range(Q):
    p,x = map(int,input().split())
    T[p][2] += x
S = []
for i in range(1,N+1):
    S.append(score(i))
print(*S)

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
C = [0 for _ in range(N+1)]
for _ in range(Q):
    p,x = map(int,input().split())
    C[p] += x
heap = deque([1])
hist = [0 for _ in range(N+1)]
while heap:
    cur = heap.popleft()
    hist[cur] = 1
    for x in G[cur]:
        if hist[x]==0:
            C[x] += C[cur]
            heap.append(x)
C.pop(0)
print(*C)