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

from collections import Counter
n = int(input())
nums = list(map(int,input().split(" ")))

c = Counter(nums)

for num in nums:
    c[num]-=1
    curr = 0
    for k,v in c.items():
        if v >=2:
            curr+= v*(v-1)//2
    print(curr)
    c[num]+=1
    

### FIXED CODE ###

from collections import Counter
n = int(input())
nums = list(map(int,input().split(" ")))

c = Counter(nums)
a = 0
for k,v in c.items():
    if v >=2:
        a+=(v-1)*v//2

for num in nums:
    curr = -1
    if c[num] >= 2:
        curr = a - (c[num]-1)
    else:
        curr = a
    print(curr)
### BUGGY CODE ###

n=int(input())
for i in range(1,3501):
  for j in range(1,3501):
    p=4*i*j-n*i-n*j
    if p>0:
      if (n*i*j)%p==0:
        print(i,j,(n*i*j)//p)
        exit()

### FIXED CODE ###

n=int(input())
for i in range(1,3501):
  for j in range(1,3501):
    if (4*i*j-n*i-n*j)!=0:
      if (n*i*j)%(4*i*j-n*i-n*j)==0 and (n*i*j)//(4*i*j-n*i-n*j)>0:
        k=(n*i*j)//(4*i*j-n*i-n*j)
        break
  else:
    continue
  break
print(i,j,k)
### BUGGY CODE ###

n = int(input())
s = str(input())
lst_ans=[]
for i in range(n):
    lst_w = s[:i]
    lst_e = s[i+1:]
    lst_ans.append(lst_w.count("W")+lst_e.count("E"))
print(min(lst_ans))

### FIXED CODE ###

n=int(input())
s=list(input())
n_W,n_E=0,0
l_W,l_E=[0],[0]
for i in s:
    if i=="W":n_W+=1
    else:n_E+=1
    l_W.append(n_W)
    l_E.append(n_E)
ans=10**9+7
for i in range(n):
    tmp=l_W[i]+l_E[-1]-l_E[i+1]
    if tmp<ans:ans=tmp
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
a = [input() for _ in range(H)]

#初期の黒("#")の位置からの距離
dist = [[-1] * W for _ in range(H)]

# "#"の位置をキューに追加
black = deque()
for h in range(H):
    for w in range(W):
        if a[h][w] == "#":
            black.appendleft((h,w))
            dist[h][w] = 0
def bfs(black, dist):
    d = 0
    while black: #blackに中身が入っている間
        h, w = black.popleft()
        d = dist[h][w]
        for dy,dx in((1,0), (0,1), (-1, 0), (0,-1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:
                dist[new_h][new_w] = d+1
                black.append((new_h, new_w))
    return d

d = bfs(black, dist)
print(d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)] #全方向調べる

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
dp_memo = [10 ** 4] * k

for i in range(1, n):
    for j in range(min(k, i)):
        dp_memo[j] = abs(h[i] - h[i - j - 1]) + dp[i - j -1]
    dp[i] = min(dp_memo)
    dp_memo = [10 ** 4] * k

print(dp[n - 1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
dp_memo = [10 ** 4] * k

for i in range(1, n):
    for j in range(min(k, i)):
        dp_memo[j] = abs(h[i] - h[i - j - 1]) + dp[i - j - 1]
    dp[i] = min(dp_memo)
    dp_memo = [10 ** 4] * k

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

from numpy import*
d=zeros(2019,int)
r=arange(2019)
a=0
for i in map(int,input()):
  p=zeros(2019,int)
  p[(r*10+i)%2019]+=d[r]
  d=p
  d[i]+=1
  a+=d[0]
print(a)

### FIXED CODE ###

a,*d=[0]*2020
for i in map(int,input()):
  p=[0]*2019
  for j in range(2019):p[(j*10+i)%2019]+=d[j]
  d=p
  d[i]+=1
  a+=d[0]
print(a)
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
sum[0][0]=dp[0][0]
for i in range(1,n):
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(1,m):
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
ans=0
for i in range(n):
  for j in range(m):
    ans+=dp[i][j]
    ans=ans%mod
print((ans+1)%mod)

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*m for _ in range(n)]
sum=[[0]*m for _ in range(n)]
mod=10**9+7
for i in range(n):
  if s[i]==t[0]:
    dp[i][0]=1
  else:
    dp[i][0]=0
for i in range(m):
  if t[i]==s[0]:
    dp[0][i]=1
  else:
    dp[0][i]=0
sum[0][0]=dp[0][0]
for i in range(1,n):
  sum[i][0]=sum[i-1][0]+dp[i][0]
for i in range(1,m):
  sum[0][i]=sum[0][i-1]+dp[0][i]
for i in range(1,n):
  for j in range(1,m):
    if s[i]==t[j]:
      dp[i][j]=(sum[i-1][j-1]+1)%mod
    else:
      dp[i][j]=0
    sum[i][j]=(sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+dp[i][j])%mod
ans=0
for i in range(n):
  for j in range(m):
    ans+=dp[i][j]
    ans=ans%mod
print((ans+1)%mod)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split(' ')))
c=0
for i in range(len(l)):
    for j in range(i+1,len(l)):
        if(l[i]==l[j]):
            print("NO")
            c=1
            break
    if(c==1):break
if(c==0):print("YES")

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split(' ')))
l.sort()
c=0
for i in range(len(l)-1):
    if(l[i]==l[i+1]):
        c=1 
        break
if(c==0):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

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

dp = [1, 0, 0, 0]
for s in S:
    newDP = [0, 0, 0, 0]
    if s == "?":
        s = "ABC"
    for i in s:
        newDP[0] += dp[0]
        newDP[1] += dp[1]
        newDP[2] += dp[2]
        newDP[3] += dp[3]
        if i == "A":
            newDP[1] += dp[0]
            newDP[1] %= mod
        elif i == "B":
            newDP[2] += dp[1]
            newDP[2] %= mod
        elif i == "C":
            newDP[3] += dp[2]
            newDP[3] %= mod
    dp = newDP

print(dp[3] % mod)

### FIXED CODE ###

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

a, ab, abc, n = 0, 0, 0, 1
for s in S:
    if s == "A":
        a += n
        a %= mod
    elif s == "B":
        ab += a
        ab %= mod
    elif s == "C":
        abc += ab
        abc %= mod
    else:
        a, ab, abc, n = 3 * a + n, 3 * ab + a, 3 * abc + ab, 3 * n
        a %= mod
        ab %= mod
        abc %= mod
        n %= mod

print(abc)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

right=0
ans=0

for left in range(n):
    right=left
    xor_sum = 0
    plus_sum = 0
    while right<n and xor_sum >= plus_sum:
        xor_sum ^= a[right]
        plus_sum += a[right]
        if xor_sum == plus_sum: ans+=1
        right+=1

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

ans=0
right=0
left=0
array_sum = 0
sum_xor = 0
sum_pls = 0

for left in range(n):

    while right<n and sum_pls+a[right] == sum_xor^a[right]:
        sum_pls += a[right]
        sum_xor ^= a[right]
        right+=1

    ans += right-left
    sum_pls -= a[left]
    sum_xor ^= a[left]

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

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,raw_input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,raw_input().split())
	d[x].add(y)
	d[y].add(x)


vis=set()
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if i not in vis:
		que=[]
		c=1
		vis.add(i)
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if j not in vis:
					vis.add(j)
					c+=1
					que.append(j)
		count=max(c,count)

print(count)













































### FIXED CODE ###

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis={i:False for i in range(1,n+1)}
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if not vis[i]:
		que=[]
		c=1
		vis[i]=True
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if not vis[j]:
					vis[j]=True
					c+=1
					que.append(j)
		count=max(c,count)

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

n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
ans = 0
b = [i[:] for i in a[:]]

for k in range(n):
    for i in range(n):
        for j in range(n):
            b[i][j] = min(b[i][j],b[i][k]+b[k][j])

flag = False
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            ans = -1
            flag = True
            break
        if b[i][j] == a[i][j]:
            for k in range(n):
                if k == i or k == j: continue
                if b[i][j] == b[i][k] + b[k][j]: break
            else:
                ans += b[i][j]
    if flag: break

ans //= 2
print(ans)

### FIXED CODE ###

n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
ans = 0
b = [i[:] for i in a[:]]

for k in range(n):
    for i in range(n):
        for j in range(n):
            b[i][j] = min(b[i][j],b[i][k]+b[k][j])

flag = False
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            ans = -1
            flag = True
            break
        if b[i][j] == a[i][j]:
            for k in range(n):
                if k == i or k == j: continue
                if b[i][j] == b[i][k] + b[k][j]: break
            else:
                ans += b[i][j]
    if flag: break

ans //= 2
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    for i, _s in enumerate(s[::-1]):
        cur = _s + cur
        mod = int(cur) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)

### FIXED CODE ###

import sys
from collections import Counter
n, p = [int(i) for i in sys.stdin.readline().split()]
s = sys.stdin.readline().strip()
if p == 2:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) % 2 == 0:
            ans += i
    print(ans)
elif p == 5:
    ans = 0
    for i, _s in enumerate(s, 1):
        if int(_s) in {0, 5}:
            ans += i
    print(ans)
else:
    us = Counter([])
    cur = ""
    ans = 0
    mod = 0
    keta_mod = 1
    for i, _s in enumerate(s[::-1]):
        keta_mod = keta_mod * 10 % p
        mod = (keta_mod * int(_s) + mod) % p
        if mod == 0:
            ans += us[mod] + 1
        else:
            ans += us[mod]
        us.update([mod])
    print(ans)
### BUGGY CODE ###

INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [0] + [INF] * H

for a, b in zip(*[iter(AB)] * 2):
    for i in range(H + 1):
        idx = i + a if i + a < H else H
        dp[idx] = dp[idx] if dp[idx] < dp[i] + b else dp[i] + b

print(dp[H])

### FIXED CODE ###

INF = float("inf")

H, N, *AB = map(int, open(0).read().split())

dp = [INF] * (H + 10 ** 4 + 10)
dp[0] = 0

for a, b in zip(*[iter(AB)] * 2):
    for i in range(a, len(dp)):
        if dp[i - a] != INF:
            dp[i] = min(dp[i], dp[i - a] + b)

print(min(dp[H:]))
### BUGGY CODE ###

l = input()
n = len(l)
mod = 10 ** 9 + 7
ans = 0
num = 1
for i in range(n):
    if l[i] == "1":
        num2 = num
        for j in range(n - i - 1):
            num2 *= 3
            num2 %= mod
        ans += num2
        num *= 2
else:
    ans += num
print(ans % mod)

### FIXED CODE ###

l = input()
n = len(l)
mod = 10 ** 9 + 7
dp = [[0 for i in range(2)] for j in range(n + 1)]
dp[0][1] = 1
for i in range(n):
    if l[i] == "1":
        dp[i + 1][0] = dp[i][0] * 3 + dp[i][1]
        dp[i + 1][0] %= mod
        dp[i + 1][1] = dp[i][1] * 2
        dp[i + 1][1] %= mod
    else:
        dp[i + 1][0] = dp[i][0] * 3
        dp[i + 1][0] %= mod
        dp[i + 1][1] = dp[i][1]
        dp[i + 1][1] %= mod
print((dp[n][0] + dp[n][1]) % mod)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) for i in range(M)]
d = {}
for i in PY:
    if i[0] in d:
        d[i[0]].append(i[1])
    else:
        d[i[0]] = [i[1]]
for k, v in d.items():
    v.sort()
for i in PY:
    print(str(i[0]).zfill(6) + str(d[i[0]].index(i[1]) + 1).zfill(6))

### FIXED CODE ###

N, M = list(map(int, input().split()))
PY = [list(map(int, input().split())) + [i, 0] for i in range(M)] 
d = {}
for i in sorted(PY, key=lambda x: x[1]):
    if i[0] in d:
        d[i[0]] += 1
    else:
        d[i[0]] = 1
    i[3] = d[i[0]]
for i in PY:
    print(str(i[0]).zfill(6) + str(i[3]).zfill(6))
### BUGGY CODE ###

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

while(N > abs(N-K)):
  N = abs(N-K)
  
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
N = N % K

while(N > abs(N-K)):
  N = abs(N-K)
  
print(N)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
if K == 1:
  print((max(P) + 1) / 2)
  exit()
elif len(list(set(P))) == 1:
  print((P[0] + 1) / 2 * K)
  exit()

sums = []
for i in range(N - K + 1):
  sums.append(sum(P[i:i + K]))
sums.sort()
print((sums[-1] + K) / 2)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
E = list(map(lambda x: (int(x) + 1) / 2, input().split()))

res = np.cumsum(E)

ans = res[K - 1]
for i in range(K, N):
    if ans < res[i] - res[i - K]:
        ans = res[i] - res[i - K]
print(ans)
### BUGGY CODE ###

n=int(input())
s=list(input())

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=0
if n>2:
  
  for x in range(n-2):
    if s[x]=='R':
      rn-=1
      ans+=gn*bn
    elif s[x]=='G':
      gn-=1
      ans+=rn*bn
    else:
      bn-=1
      ans+=gn*rn
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)

### FIXED CODE ###

n=int(input())
s=list(input())

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)
### BUGGY CODE ###

X = int(input())
if X < 100:
    print(0)
else:
    item = [100, 101, 102, 103, 104, 105]
    dp = [[False for _ in range(X//100+10)] for _ in range(X+10)]
    dp[0][0] = True
    dp[100][1] = True
    dp[101][1] = True
    dp[102][1] = True
    dp[105][1] = True
    for x in range(100, X+1):
        for n in range(1, X//100+4):
            for i in item:
                if dp[x-i][n-1]:
                    dp[x][n] = True
    if True in dp[x]:
        print(1)
    else:
        print(0)

### FIXED CODE ###

X = int(input())
dp = [False for _ in range(X+1)]
dp[0] = True
for x in range(X+1):
    if x > 99:
        item = [100, 101, 102, 103, 104, 105]
        for i in item:
            if dp[x-i]:
                dp[x] = True
if dp[X]:
    print(1)
else:
    print(0)
### BUGGY CODE ###

import sys
from itertools import combinations
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(enumerate(map(int, readline().split()), 1))

ans = 0
for (i, b), (j, c) in combinations(a, 2):
  # print(f'{i=} {b=} {j=} {c=} {i-j=} {b+c=}')
  if abs(i - j) == abs(b + c):
    ans += 1

print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
n = int(readline())
a = list(map(int, readline().split()))
b = defaultdict(list)
c = defaultdict(list)

for i, v in enumerate(a, 1):
  b[i + v].append(i)
  if 2 <= i - v <= 100000001:
    c[i - v].append(i)
c = dict(c)

ans = 0
for v, L in b.items():
  for j in L:
    if v in c:
      ans += len(c[v])
print(ans)
### BUGGY CODE ###

n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

n=int(input())
a=[[int(x)-1 for x in input().split()] for _ in range(n)]

cnt=0
id=[[0]*n for _ in range(n)]
for i in range(n):
	for j in range(i+1,n):
		id[i][j] = cnt
		cnt+=1
def toid(x,y):
	return id[x][y] if x<y else id[y][x]

for i in range(n):
	for j in range(n-1):
		a[i][j] = toid(i,a[i][j])

nedge = n*(n-1)//2
g=[[]for _ in range(nedge)]
to = [0]*nedge
for i in range(n):
	for j in range(1,n-1):
		g[a[i][j-1]].append(a[i][j])
		to[a[i][j]]+=1

from collections import deque

dp=[1]*nedge
q=deque([])
cnt = 0
for i in range(nedge):
	if to[i]==0:
		q.append(i)
		cnt+=1

ans = 1
while(q):
	e = q.popleft()
	for ne in g[e]:
		dp[ne] = max(dp[ne],dp[e]+1)
		to[ne]-=1
		if to[ne]==0:
			q.append(ne)
			cnt+=1
	ans = max(ans,dp[e])

if cnt != nedge:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

import numpy as np
n = int(input())
A = [[0]*n for _ in range(n)]
for i in range(n-1):
  A[i][i]=A[i][i+1]=1
A[n-1][0]=A[n-1][n-1]=1
b = list(map(lambda x:int(x)*2,input().split()))
A = np.array(A)
b = np.array(b)
x = np.linalg.solve(A,b)
for i in x:
  print(int(i),end=" ")

### FIXED CODE ###

n = int(input())
li = list(map(lambda x:int(x)*2,input().split()))
num = 0
for i,b in enumerate(li[1:]):
  if i%2==0:
    num += b
  else:
    num -= b
x = (li[0]-num)//2
print(x,end=" ")
for i in range(n-1):
  x = li[i]-x
  print(x,end=" ")
### BUGGY CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1), np.int64)
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
print(max(dp[-1]))

### FIXED CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))
### BUGGY CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0
def dfs(node, parent):
    global ans
    cnt = 1
    cnt = sum(dfs(child, node) for child in adj[node] if child != parent) + 1
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

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

cumpro=[]

pro=1
for i in range(n):
    if i<k:
        pro*=a[i]
        cumpro.append(pro)
    else:
        pro/=a[i-k]
        pro*=a[i]
        cumpro.append(pro)

for j in range(k,n):
    if cumpro[j]>cumpro[j-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(k,n):
    if a[i]>a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
L = []
cnt = 0
for i in range(M):
    L.append(list(map(int, input().split())))
sL = sorted(L, key=lambda x:x[1], reverse = True)

for i in range(M):
    if cnt > N:
        break
    if L[i][1] <= min(A):
        pass
    else:
        for j in range(L[i][0]):
            A.append(L[i][1])
            A.remove(min(A))
            cnt += 1
            if cnt > N:
                break

sA = sorted(A, reverse = True)
print(sum(sA[:N]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
K = [1] * N
L = list(zip(K,A))
for i in range(M):
	L.append(list(map(int, input().split())))
S = sorted(L, key = lambda x:x[1], reverse = True)
sum = 0
cnt = 0
for i in range(N):
	if N - cnt <= S[i][0]:
		sum += S[i][1] * (N - cnt)
		break
	else:
		sum += S[i][1] * S[i][0]
		cnt += S[i][0]
print(sum)
### BUGGY CODE ###

import itertools
N, M, Q = map(int, input().split())
abcd = []
ans = 0
for i in range(Q):
  abcd.append(input())
for X in itertools.combinations_with_replacement(range(1, M + 1), N):
  tmp = 0
  for z in abcd:
    a, b, c, d = map(int, z.split())
    if X[b - 1] - X[a - 1] == c:
      tmp += d
  ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
abcd = []
ans = 0
for i in range(Q):
  abcd.append(input())
for X in itertools.combinations_with_replacement(range(1, M + 1), N):
  tmp = 0
  for z in abcd:
    a, b, c, d = map(int, z.split())
    if X[b - 1] - X[a - 1] == c:
      tmp += d
  ans = max(ans, tmp)
print(ans)