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

import collections
n,x,y=map(int,input().split())
import heapq


class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

route_map = [dict() for _ in range(n)]
route_map[x-1][y-1]=1
route_map[y-1][x-1]=1
for i in range(n-1):
    route_map[i][i+1] = 1
    route_map[i+1][i]=1    
lst=[]
for i in range(n):
    lst+=Dijkstra(route_map,i).execute()        
Lst=list(collections.Counter(lst).items())
Key=list(collections.Counter(lst).keys())
m=max(Key)
for i in range(1,m+1):
    print(Lst[i][1]//2)
for i in range(m+1,n):
    print(0)


### FIXED CODE ###

import collections
n,x,y=map(int,input().split())
lst=[]
num=[0]*(n+1)
for i in range(1,n):
  for j in range(i+1,n+1):
    k=min(abs(i-j),abs(i-x)+1+abs(j-y),abs(i-y)+1+abs(j-x))
    if num[k]==0:
      num[k]+=1
    lst.append(k)
    
Lst=list(collections.Counter(lst).items())
key=0
for i in range(1,n):
  if num[i]==0:
    print(0)
  else:
    print(Lst[key][1])
    key+=1
### BUGGY CODE ###

n,ma,mb=map(int,input().split())
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])
from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**18 for i in range(401)]for j in range(401)]
dp[0][0]=0

q=[[0,0]]
for a,b,c in abc:
    l=[]
    for i,j in q:
        l.append([i,j])
        l.append([i+a,j+b])
        dp[a+i][b+j]=min(dp[a+i][b+j],dp[i][j]+c)
    q=l

ans=1145141919
i=1
while ma*i<401 and mb*i<401:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print(-1)
else:
    print(ans)





### FIXED CODE ###

n,ma,mb=map(int,input().split())
abc=[]
for i in range(n):
    abc.append([int(j) for j in input().split()])
from operator import itemgetter
abc.sort(key=itemgetter(2))

dp=[[10**18 for i in range(401)]for j in range(401)]
dp[0][0]=0

p,q=0,0
for a,b,c in abc:
    for j in reversed(range(q+1)):
        for i in range(p+1):
            if dp[i][j]==10**18:
                continue
            else:
                dp[i+a][j+b]=min(dp[i+a][j+b],dp[i][j]+c)
    p+=a
    q+=b

ans=1145141919
i=1
while ma*i<401 and mb*i<401:
    ans=min(ans,dp[ma*i][mb*i])
    i+=1
if ans==1145141919:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n=int(input())
S=input()
dictR=[]
dictG=[]
dictB=[]
r=0
g=0
b=0
r=S.count("R")
g=S.count("G")
b=S.count("B")
sum=r*g*b
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            si=S[i]
            sj=S[j]
            sk=S[k]
            if k-j==j-i and(si!=sj and sj!=sk and si!=sk):
                sum-=1



print(sum)

### FIXED CODE ###

n=int(input())
S=input()
R={}
G={}
B={}
r=0
g=0
b=0
for i in range(n):
    if S[i] == 'R':
        R[i] = None
    elif S[i] == 'G':
        G[i] = None
    else:
        B[i] = None
cnt=len(R)*len(G)*len(B)
for b in B:
    for g in G:
        if (b+g)/2 in R:
            cnt-=1
for b in B:
    for r in R:
        if (b+r)/2 in G:
            cnt-=1
for r in R:
    for g in G:
        if (r+g)/2 in B:
            cnt-=1
print(cnt)
### BUGGY CODE ###

import bisect
N=int(input())
S=list(input())
ans=0
R=[]
G=[]
B=[]
for i in range(N):
    if S[i]=="R":
        R.append(i+1)
    elif S[i]=="G":
        G.append(i+1)
    else:
        B.append(i+1)
ans=len(B)*len(R)*len(G)
B.append(10000)
lenb=len(B)-1
flag=0
for r in R:
    for g in G:
        left=min(r,g)-abs(r-g)
        right=max(r,g)+abs(r-g)
        if (r+g)%2==0:
            middle=(r+g)//2
        else:
            middle=0
        for i in (left,right,middle):
            if i>0:
                a=bisect.bisect_left(B,i)
                if B[a]==i:
                    flag=flag+1
ans=ans-flag
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
ans=0
R=0
G=0
B=0
for i in range(N):
    if S[i]=="R":
        R=R+1
    elif S[i]=="G":
        G=G+1
    else:
        B=B+1
ans=R*G*B
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i]!=S[j]:
            k=2*j-i
            if N<=k:
                continue
            if S[i]!=S[k] and S[k]!=S[j]:
                ans=ans-1
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
li = na()
ls = []
if len(li) - 1 < n - 1:
    print(0)
else:
    list.sort(li)
    for i in range(len(li) - 1):
        ls.append(li[i + 1] - li[i])
    for j in range(n - 1):
        ls.remove(max(ls))
    print(sum(ls))

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
li = na()
ls = []
list.sort(li)
for i in range(len(li) - 1):
    ls.append(li[i + 1] - li[i])
ls = sorted(ls, reverse=True)
print(sum(ls[n-1:]))
### BUGGY CODE ###

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())

dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, -1, - 1):
        v = dp[j] + v_list[i]
        if j + w_list[i] <= w and dp[j + w_list[i]] < v:
            dp[j + w_list[i]] = v
print(dp[-1])

### FIXED CODE ###

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

w_list = [0] * n
v_list = [0] * n
for i in range(n):
    w_list[i], v_list[i] = map(int, input().split())

dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, -1, - 1):
        v = dp[j] + v_list[i]
        if j + w_list[i] <= w and dp[j + w_list[i]] < v:
            dp[j + w_list[i]] = v
print(dp[-1])
### BUGGY CODE ###

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

sum_p = 0
sum_list = []
sum_list.append(sum_p)
for p_element in p:
    sum_p += p_element 
    sum_list.append(sum_p)

sum = 0
for i in range(N-K+1):
    if sum < sum_list[i+K]-sum_list[i]:
        sum = sum_list[i+K]-sum_list[i]
        select_list = []
        for j in range(K):
            select_list.append(p[i+j])

answer = 0
for i in select_list:
    answer += (1+i)/2
print(answer)

### FIXED CODE ###

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

sum_p = 0
sum_list = []
sum_list.append(sum_p)
for p_element in p:
    sum_p += p_element 
    sum_list.append(sum_p)

sum = 0
start = 0
for i in range(N-K+1):
    if sum < sum_list[i+K]-sum_list[i]:
        sum = sum_list[i+K]-sum_list[i]
        start = i

answer = 0
for i in range(K):
    answer += (1+p[start+i])/2
print(answer)
### BUGGY CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

from numpy.linalg import solve

N =ii()
left = dp2(0, N, N)
for i in range(N-1):
    left[i][i] = left[i][i+1] = 0.5
left[N-1][N-1] = left[N-1][0] = 0.5

right = li()

for i in solve(left, right):
    print(int(i), end='')
    print(' ', end='')

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

'''
from numpy.linalg import solve

N =ii()
left = dp2(0, N, N)
for i in range(N-1):
    left[i][i] = left[i][i+1] = 0.5
left[N-1][N-1] = left[N-1][0] = 0.5

right = li()

for i in solve(left, right):
    print(int(i), end='')
    print(' ', end='')
'''

N = ii()
A = li()

ans = [0]*N

ans[0] = sum(A) - sum([A[i] for i in range(1, N, 2)])*2
for i in range(N-1):
    ans[i+1] = A[i]*2 - ans[i]

for i in range(N):
    print(ans[i], end='')
    print(' ', end='')
### BUGGY CODE ###

#! /usr/bin/python3
# Between a and b ...

"""
非負の整数 a, b (a≤b) と、正の整数 x が与えられます。
a 以上 b 以下の整数のうち、x で割り切れるものの個数を求めてください。
"""

test_mode = False

a, b, x = map(int, input().split())
counter = 0

for num in range(a, b+1):
    if num % x == 0:
        counter += 1
        if test_mode:
            print(num, num%x == 0, counter)

print(counter)


### FIXED CODE ###

#! /usr/bin/python3
# Between a and b ...

"""
非負の整数 a, b (a≤b) と、正の整数 x が与えられます。
a 以上 b 以下の整数のうち、x で割り切れるものの個数を求めてください。
"""

test_mode = False

a, b, x = map(int, input().split())

if a%x != 0:
    limit_min = a//x +1
else:
    limit_min = a//x

limit_max = b//x


ans = limit_max - limit_min + 1

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

import copy
# In=[list(map(int,i.split())) for i in Input.split('\n')]
# N=In[0][0]
# A=In[1]
N=int(input())
I=list(map(int,input().split()))
for j in range(N):
    counter=[0 for i in range(N+1)]
    A=copy.deepcopy(I)
    A.pop(j)
    B=[]
    for i in A:
        counter[i]+=1
    for i in counter:
        if i>1:
            B.append(i*(i-1)/2)
    print(int(sum(B)))

### FIXED CODE ###

import copy
# In=[list(map(int,i.split())) for i in Input.split('\n')]
# N=In[0][0]
# A=In[1]
N=int(input())
A=list(map(int,input().split()))
counter=[0 for i in range(N+1)]
ans2=[0 for i in range(N+1)]
B=[]
for i in A:
    counter[i]+=1
ans=[0 for i in range(N+1)]
for i,value in enumerate(counter):
    if value>0:
        ans[i]=(value*(value-1)//2)
        ans2[i]=((value-1)*(value-2)//2)
total=sum(ans)
for i in A:
    temp=total
    temp-=ans[i]
    temp+=ans2[i]
    print(temp)
### BUGGY CODE ###

N, M, Q = map(int, input().split())
# LR = [list(map(int, input().split())) for i in range(M)]
Ls = [set() for i in range(N)]
Rs = [set() for i in range(N)]
for i in range(M):
  L, R = map(int, input().split())
  Ls[L-1].add(i)
  Rs[R-1].add(i)

for i in range(N-1):
  j = N - 1 - i
  Rs[i+1] |= Rs[i]
  Ls[j-1] |= Ls[j]

for i in range(Q):
  p, q = map(int, input().split())
  print(len(Ls[p-1] & Rs[q-1]))

### FIXED CODE ###

N, M, Q = map(int, input().split())
MAP = [[0] * N for i in range(N)]
for i in range(M):
  L, R = map(int, input().split())
  MAP[L-1][R-1] += 1

for r in range(N):
  for l in range(N-1, 0, -1):
    MAP[l-1][r] += MAP[l][r]

for r in range(N-1):
  for l in range(N):
    MAP[l][r+1] += MAP[l][r]

for i in range(Q):
  p, q = map(int, input().split())
  print(MAP[p-1][q-1])
### BUGGY CODE ###

N,Q = (int(X) for X in input().split())
S = input()
for T in range(0,Q):
    L,R = (int(X) for X in input().split())
    print(S[L-1:R].count('AC'))

### FIXED CODE ###

N,Q = (int(X) for X in input().split())
S = input()
T = [0]*(N+1)
for I in range(0,N):
     T[I+1] = T[I] + (S[I:I+2]=='AC')
for J in range(0,Q):
    L,R = (int(X)-1 for X in input().split())
    print(T[R]-T[L])
### BUGGY CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
sA = set(A)
ans = 0
for num in sA:
    if A.count(num) % 2 == 1:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
#sA = set(A)
ans = 0
for num in Counter(A).values():
    #print(num)
    if num % 2 == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int( input() )

judge_nums = []
for i in range( n ):
	judge_num = 10**27 # 一桁目はフェイク
	str = input()
	for s in str :
		judge_num += 10**(ord( s )-97)
	judge_nums.append( judge_num )
judge_nums = sorted( judge_nums )


count = 0
for i in range( n ) :
	bFound = False
	for j in range( i+1, n ) :
		if judge_nums[i] != judge_nums[j] :
			break
		if judge_nums[i] == judge_nums[j] :
			count += 1
			bFound = True

print( count )



### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#=-------------------------------------  
n = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

class Dict(object):

    m1 = 1046527
    m2 = m1 - 1

    def __init__(self):
        self._dict = [""] * self.m1

    def insert(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == "":
                self._dict[ix] = k
                return
            else:
                i += 1

    def find(self, k):
        i = 0

        while True:
            ix = self._h(k, i)
            if self._dict[ix] == k:
                return True
            elif self._dict[ix] == "":
                return False
            else:
                i += 1

        return False

    def _h(self, k, i):
        return (self._h1(k) + i * self._h2(k)) % self.m1

    def _h1(self, k):
        return k % self.m1

    def _h2(self, k):
        return k % self.m2 + 1


def to_int(s):
    ret = 0
    i = 1
    for j in range(len(s)):
        e = s[len(s) - j - 1]

        if e == 'A':
            ret += 1 * i
        elif e == 'C':
            ret += 2 * i
        elif e == 'G':
            ret += 3 * i
        elif e == 'T':
            ret += 4 * i
        i *= 5

    return ret


if __name__ == '__main__':
    n = int(input())

    d = Dict()

    for _ in range(n):
        cmd, val = input().split()

        if cmd == "insert":
            d.insert(to_int(val))
        else:
            ans = "yes" if d.find(to_int(val)) else "no"
            print(ans)

### FIXED CODE ###

M = 1046527
L = 14
H = [""] * M
 
def getChar(ch):
    if ch == 'A':
        return 1
    elif ch == 'C':
        return 2
    elif ch == 'G':
        return 3
    elif ch == 'T':
        return 4
    else:
        return 0
 
def getKey(strings):
    Sum = 0
    p = 1
    for i in xrange(len(strings)):
        Sum += p * getChar(strings[i])
        p *= 5
 
    return Sum
 
def h1(key):
    return key % M
 
def h2(key):
    return 1 + (key % (M-1))
 
def find(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            return 0
        else:
            i += 1
    return 0
 
def insert(strings):
    key = getKey(strings)
    i = 0
    while True:
        h = (h1(key) + i * h2(key)) % M
        if H[h] == strings:
            return 1
        elif len(H[h]) == 0:
            H[h] = strings
            return 0
        else:
            i += 1
    return 0
 
def main():
    n = input()
    for i in xrange(n):
        com = raw_input().split()
        if com[0][0] == 'i':
            insert(com[1])
        else:
            if find(com[1]):
                print 'yes'
            else:
                print 'no'
    return 0
 
main()
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
score = 1
for i in range(k):
    score *= a[i]

for i in range(k, n):
    if a[i] > a[i - k]:
        print('Yes')
    else:
        print('No')
    score *= a[i]

### 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 ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 約数
N = ir()
A = lr()
A.sort()
answer = 0
bl = [0] * (10**6+1)

def make_divisors(n):  # 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

for i, a in enumerate(A):
    if i < N-1 and a == A[i+1]:
        bl[a] = 1
        continue
    divs = make_divisors(a)
    flag = True
    for x in divs:
        if bl[x] == 1:
            flag = False
            break
    bl[a] = 1
    if flag:
        answer += 1

print(answer)


### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
A.sort()
bl = [True] * (A[-1]+1)
answer = 0
for i, a in enumerate(A):
    if i < N-1 and A[i+1] == a:
        pass
    elif bl[a]:
        answer += 1
    if bl[a]:
        bl[a] = False
        next = a + a
        while next <= A[-1]:
            bl[next] = False
            next += a

print(answer)
### BUGGY CODE ###

n, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

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

for i in range(n):
    for w in range(W+1):
        if w >= wv[i][0]:
            dp[i+1][w] = max(
                dp[i][w - wv[i][0]] + wv[i][1],
                dp[i][w]
            )
        else:
            dp[i+1][w] = dp[i][w]

print(dp[n][W])

### FIXED CODE ###

N, W = map(int, input().split())
item = [list(map(int, input().split())) for i in range(N)]

dp = [[0]*(W+1) for i in range(N+1)]
for i in range(N):
    for w in range(1, W+1):
        if w - item[i][0] >= 0:
            dp[i+1][w] = max(
                dp[i][w],
                dp[i][w-item[i][0]] + item[i][1]
            )
        else:
            dp[i+1][w] = dp[i][w]
print((dp[N][W]))
### BUGGY CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
for k in range(n):
	dic = collections.Counter(li)
	dic[li[k]] -=1
	x = 0
	for d in dic.values():
		x+= int(d*(d-1)*0.5)
	print(x)

### FIXED CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
collections.Counter(li)
m = 0
dic = collections.Counter(li)
for i in dic.values():
    m += int(i*(i-1)*0.5)
for k in range(n):
      print(m-dic[li[k]]+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
INF=10**18
c=[]
for i in range(n):
  for j in range(i+1,n):
    c+=[(i,j)]
d=dict(zip(c,[[] for _ in range(n*(n-1)//2)]))
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=(i,a[0]-1)
  else:b=(a[0]-1,i)
  s+=[b]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[(i,j)]
      b=(i,j)
    else:
      d[b]+=[(j,i)]
      b=(j,i)
vis=dict(zip(c,[0]*(n*(n-1)//2)))
day=dict(zip(c,[-1]*(n*(n-1)//2)))
ans=0
for i in s:
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(now):
  res=day[now]
  if vis[now]:
    if res==-1:return -1
    else:return res
  res=1
  vis[now]=1
  for to in d[now]:
    r=dfs(to)
    if r==-1:return -1
    res=max(res,r+1)
  day[now]=res
  return res
n=int(input())
v=0
si=[[0]*n for _ in range(n)]
for i in range(n):
  for j in range(i+1,n):
    si[i][j]=v
    v+=1
d=[[] for _ in range(v)]
s=[]
for i in range(n):
  a=list(map(int,input().split()))
  if i<a[0]-1:b=si[i][a[0]-1]
  else:b=si[a[0]-1][i]
  for j in a[1:]:
    j-=1
    if i<j:
      d[b]+=[si[i][j]]
      b=si[i][j]
    else:
      d[b]+=[si[j][i]]
      b=si[j][i]
vis=[0]*v
day=[-1]*v
ans=0
for i in range(v):
  di=dfs(i)
  if di==-1:
    print(-1)
    exit()
  ans=max(ans,di)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [input() for i in range(n)]
b = []
for i in range(n):
  b.append(''.join(sorted(a[i])))
c = list(set(b))
cnt = []
for i in range(len(c)):
  cnt.append(b.count(c[i]))
ans = 0
for i in cnt:
  ans += int(i*(i-1)/2)
print(ans)

### FIXED CODE ###

N = int(input())
s_sort = [''.join(sorted(input())) for _ in range(N)]
dic = {}
ans = 0
for i in s_sort:
  if i not in dic:
    dic[i] = 0
  else:
    dic[i] += 1
    ans += dic[i]
print(ans)