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

h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min(filter(lambda x :x>0,dp[h:]))
print(ans)
#print(dp)



### FIXED CODE ###

h,n = map(int,input().split())
skills = []
for _ in range(n):
  a,b = map(int,input().split())
  skills.append((a,b))
dp = [float('inf') for _ in range(h+max(skills,key=lambda x:x[1])[1] + 1)]
dp[0] = 0
  
for i in range(len(dp)):
  if dp[i] ==float('inf'):
    continue
  for damage,mp in skills:
    if i+damage >= len(dp):
      continue
    if dp[i+damage] > dp[i] + mp:
      dp[i+damage] = dp[i]+mp
ans = min(filter(lambda x :x>0,dp[h:]))
print(ans)
#print(dp)
### BUGGY CODE ###

import copy
N,K = map(int,input().split())
A = map(int,input().split())

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

max_num = max(score)
i = 0
while(True):
    if(2**(i+1)>max_num):
        break
    else:
        i+=1

ans = 0
for j in range(i,-1,-1):
    if len(score)<K:
        break
    count = 0
    score_a = []
    score_b = []
    for k in range(len(score)):
        if score[k] >= 2**j:
            count += 1
            score[k] -= 2**j
            score_a.append(score[k])
        score_b.append(score[k])
    if count >= K:
        ans += 2**j
        score = copy.deepcopy(score_a)
    else:
        score = copy.deepcopy(score_b)

print(ans)


### FIXED CODE ###

import copy
N,K = map(int,input().split())
A = map(int,input().split())

A_sum = [0]
for a in A:
    A_sum.append(A_sum[-1]+a)

score = []
for r in range(1,N+1):
    for l in range(0,r):
        score.append(A_sum[r]-A_sum[l])

ans = 0
for i in range(40,-1,-1):
    count = 0
    score_a = []
    for j in score:
        if (j & (1<<i)):
            count += 1
            score_a.append(j)
    if count >= K:
        ans += (1<<i)
        score = copy.deepcopy(score_a)

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

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
revS = S[::-1]
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if revS[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(revS[0]) % MOD1] += 1

for i in range(1, N):
    if revS[i] == '?':
        for k in range(10):
            for j in range(MOD1):
                dp[i][(k * 10 ** i + j) % MOD1] += dp[i - 1][j]
                dp[i][(k * 10 ** i + j) % MOD1] %= MOD2

    else:
        for j in range(MOD1):
            dp[i][(int(revS[i]) * 10 ** i + j) % MOD1] += dp[i - 1][j]
            dp[i][(int(revS[i]) * 10 ** i + j) % MOD1] %= MOD2

print(dp[-1][5])


### FIXED CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
                dp[i + 1][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]
            dp[i + 1][tmp_j] %= MOD2

print(dp[-1][5] % MOD2)
### BUGGY CODE ###

import numpy as np
n,k,q = map(int, input().split())
a = [int(input()) for i in range(q)]
win = [0 for _ in range(n)]
p = np.array([k for _ in range(n)])
for ai in a:
  p -= 1
  p[ai-1] += 1
for pi in p:
  if pi<=0: print('No')
  else: print('Yes')

### FIXED CODE ###

import numpy as np
n,k,q = map(int, input().split())
a = [int(input()) for i in range(q)]
#cnt = [0 for _ in range(n)]
win = [0 for _ in range(n)]
#p = np.array([k for _ in range(n)])
for ai in a:
  win[ai-1] += 1
#print(win)

for w in win:
  if k-q+w<=0: print('No')
  else: print('Yes')
### BUGGY CODE ###

import numpy as np
import itertools

n = int(input())
ans =0
for a,b,c in itertools.product(range(1,n+1),repeat=3):

    g = np.gcd(np.gcd(a,b),c)
    ans +=g
print(ans)

### FIXED CODE ###

import numpy as np
K = int(input())
l = [0] *(K+1)
res = 0
for i in range(1,K+1):
    for j in range(1, K+1):
        gcd_ab = np.gcd(i,j)
        l[gcd_ab] +=1

for i in range(1, K+1):
    for j in range(1,K+1):
        gcd_c = np.gcd(i,j)
        res += l[j]* gcd_c


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

N,M=map(int, input().split())
P=[]
S=[]
for i in range(M):
    p,s=input().split()
    P.append(int(p))
    S.append(s)


import numpy as np
P=np.array(P)
S=np.array(S)

if M>0:
    ans=np.unique(P[S=="AC"])

    wa=0
    for j in ans:
        for i in S[P==j]:
            if i=="WA":
                wa+=1
            else:
                break

    print(len(ans),wa)
else:
    print(0,0)

### FIXED CODE ###

N,M=map(int,input().split())
AC={}
WA={}
for i in range(M):
    a,b=input().split()
    if not(a in AC.keys()):
        if b=="AC":
            AC[a]=1
        else:
            if a in WA.keys():
                WA[a]+=1
            else:
                WA[a]=1
y=0
for i in AC.keys():
    if i in WA.keys():
        y+=WA[i]
print(sum(AC.values()),y)
### BUGGY CODE ###

num=10**5
for i in range(num):
  [0 for _ in range(num)]


### FIXED CODE ###

import numpy as np
from numba import njit

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

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
for i in range(len(a) - 1, -1, -1):
    if sum(a[:i]) * 2 < a[i]:
        break
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
strength = [0] * (n + 1)
for i in range(1, n):
    strength[i] = strength[i - 1] + a[i - 1]
for i in range(len(a) - 1, -1, -1):
    if strength[i] * 2 < a[i]:
        break
    ans += 1
print(ans)
### BUGGY CODE ###

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

a.sort(reverse=True)

while m > 0 :
  m -= 1
  a[0] = a[0]//2
  a.sort(reverse=True)

print(sum(a))



### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(lambda x : int(x) * (-1),input().split()))

heapq.heapify(a)

while m > 0 :
  m -= 1
  heapq.heappush(a, -(-heapq.heappop(a) // 2))

print(-sum(a))
### BUGGY CODE ###

a = int(input())
cnt = 1
count =0
for i in range(1,a):
    for j in range(1,a):
        if a>i*j:
          count +=1
        else:
          break
print(count)

### FIXED CODE ###

a = int(input())
cnt = 1
count =0
for i in range(1,a):
    for j in range(1,a):
        if a>i*j:
          count +=1
        else:
          break
            
print(count)
### BUGGY CODE ###

MOD = 10**9+7
def resolve():
    H, W = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]
    import collections
    maxdist = 0
    for startx in range(H):
        for starty in range(W):
            if S[startx][starty] == "#":
                continue
            visited = [[False for _ in range(W)] for __ in range(H)]
            q = collections.deque([(startx, starty, 0)])
            while q:
                x, y, dist = q.pop()
                visited[x][y] = True
                maxdist = max(maxdist, dist)
                for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "#" and visited[nx][ny] is False:
                        q.appendleft((nx, ny, dist+1))
    print(maxdist)
    

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    H, W = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]
    import collections
    maxdist = 0

    for startx in range(H):
        for starty in range(W):
            if S[startx][starty] == "#":
                continue
            visited = [[-1 for _ in range(W)] for __ in range(H)]
            visited[startx][starty] = 0
            q = collections.deque([(startx, starty)])
            while q:
                x, y = q.pop()
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "#" and visited[nx][ny] == -1:
                        visited[nx][ny] = visited[x][y] + 1
                        q.appendleft((nx, ny))
            maxdist = max(maxdist,max(sum(visited, [])))
    print(maxdist)
    

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

import collections


def main():
    n = int(input())
    s = [input() for _ in range(n)]
    d = []
    ans = 0
    for ss in s:
        c = collections.Counter(ss)
        d.append(c)
    for i in range(n):
        for j in range(i + 1, n):
            if d[i] == d[j]:
                ans += 1              
    print(ans)  
        
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def main():
    n = int(input())
    d = {}
    ans = 0
    
    for _ in range(n):
        ss = ''.join(sorted(input()))
        d[ss] = d.get(ss, 0) + 1
        
    for k, v in d.items():
        if v != 1:
            ans += combinations_count(v, 2)
         
    print(ans)
       
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque([])
for _ in range(N):
    A.append(int(input())-1)
b = 0
cnt = 0
pushed = deque([0])
while b != 1:
    cnt += 1
    b = A[b]
    if b in pushed:
        print(-1)
        break
    pushed.append(b)
else:
    print(cnt)

### FIXED CODE ###

from collections import deque
N = int(input())
A = deque([])
for _ in range(N):
    A.append(int(input())-1)
b = 0
cnt = 0
for i in range(N):
    cnt += 1
    b = A[b]
    if b == 1:
        print(cnt)
        break
else:
    print(-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

a,b,c,k=mii()


ans=0
for i in range(k):
    if a>0:
        ans+=1
        a-=1
    elif b>0:
        b-=1
    else:
        ans-=1
        c-=1
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

a,b,c,k=mii()


ans=0

for i,abc in [[a,"a"],[b,"b"],[c,"c"]]:
    if k<i:
        if abc=="a":
            ans+=k
            k=0
        elif abc=="b":
            ans+=0
            k=0
        else:
            ans-=k
            k=0
    else:
        if abc=="a":
            ans+=a
            k-=a
        elif abc=="b":
            ans+=0
            k-=b
        else:
            ans-=c
            k-=c
    if k==0:
        print(ans)
        exit()
print(ans)
### BUGGY CODE ###

def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append([v-1,a,b])
    g[v-1].append([u-1,a,b])
  import heapq
  from collections import defaultdict
  import math
  dp=[[math.inf]*(100*51)for _ in range(n)]
  kakutei=[[0]*(100*51)for _ in range(n)]
  dp[0][min(s,100*51-1)]=0
  todo=[[0,0,min(s,100*51-1)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[math.inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(100*51-1,i+c)
    dp[v][j]=min(dp[v][j],dp[v][i]+d)
    heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
  #for i in range(n):
  #  print(dp[i][:10])
if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

from functools import reduce
import operator
import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if not ANS[idx]:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if not ANS[i] : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if not ANS[i] : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
parameter = 0.9975
INIT = None
ANS = [INIT]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

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

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

r, g, b, n = (int(i) for i in input().split())  
 
rmax = int(n/r)
gmax = int(n/g)
count = 0
i = 0
j = 0
k = 0

for i in range(0, rmax + 1):
  for j in range(0, gmax + 1):
    if ((n - r * i - g * j) % b == 0 and (n - r * i - g * j)>=0):
      count += 1
  
print(count)

### FIXED CODE ###

r, g, b, n = (int(i) for i in input().split())  
 
rmax = int(n/r)
count = 0
 
for i in range(0, rmax + 1):
  gmax = (n - r * i) // g
  for j in range(0, gmax + 1):
    tmp = n - r * i - g * j
    if (tmp % b == 0 and tmp >=0):
      count += 1
  
print(count)
### BUGGY CODE ###

n=int(input())
L=list(map(int, input().split()))
s=max(L)

from math import factorial
c=0
for i in range(n):	
	d=factorial(s)/factorial(L[i])/factorial(s-L[i])
	if d>=c and L[i]!=s:
		c=d
		a=L[i]
A=[s, a]
print(*A)

### FIXED CODE ###

n=int(input())
L=list(map(int, input().split()))
a=max(L)
b=a
c=0
for i in range(n):
	if b>=abs(L[i]-a/2) and L[i]!=a:
		b=abs(L[i]-a/2)
		c=L[i]


print(a,c)
### BUGGY CODE ###

n = int(input())
dict = {}
for _ in range(n):
    s = input()
    if s in dict:
        dict[s] += 1
    else:
        dict[s] = 0
max_list = [k for k, v in dict.items() if v == max(dict.values())]
max_list.sort()
for i in max_list:
    print(i)

### FIXED CODE ###

n = int(input())
dict = {}
for _ in range(n):
    s = input()
    if s in dict:
        dict[s] += 1
    else:
        dict[s] = 0
max_val = max(dict.values())
max_list = [k for k, v in dict.items() if v == max_val]
max_list.sort()
for i in max_list:
    print(i)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = A[0]
    for v in A:
        tmp = gcd(g, v)
        g = g * v // tmp
    ret = 0
    for v in A:
        ret += g // v
        ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    def factorize(n):
        ret = {}
        d = 2
        mx = int(n ** 0.5) + 1
        while d < mx:
            if n % d == 0:
                ret[d] = 0
            while n % d == 0:
                ret[d] += 1
                n //= d
            d += 1
        if n > 1:
            if n not in ret:
                ret[n] = 1
            else:
                ret[n] += 1
        return ret
    divs = {}
    cur = 1
    ret = 0
    for val in A:
        facs = factorize(val)
        tmp = 1
        for k, cnt in facs.items():
            if not k in divs:
                divs[k] = 0
            if divs[k] < cnt:
                tmp *= k ** (cnt - divs[k])
                divs[k] = cnt
        cur *= tmp
        ret *= tmp
        ret += cur // val
        ret %= MOD
        #print(tmp, cur)
        #print(divs)
        #print(ret)
        #print('-------')
    print(ret)
    return ret

def solve_(N: int, A: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = A[0]
    for v in A:
        tmp = gcd(g, v)
        g = g * v // tmp
    ret = 0
    for v in A:
        ret += g // v
        ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

from collections import defaultdict, deque

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

connect_dic = defaultdict(list)

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

query_weight = defaultdict(int)
for _ in range(Q):
    q, x = map(int, input().split())
    query_weight[q] += x

used = set()
dq = deque([1])
used.add(1)
ans = [0] * (N + 1)

while dq:
    node = dq.popleft()
    can = connect_dic[node]

    used.add(node)
    ans[node] += query_weight[node]

    for c in can:
        if c not in used:
            ans[c] += ans[node]
            dq.append(c)


ans = [str(w) for w in ans[1:]]
print(' '.join(ans))


### FIXED CODE ###

from collections import deque

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

connect_lst = [[] for _ in range(N + 1)]

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

query_weight = [0] * (N + 1)
for _ in range(Q):
    q, x = map(int, input().split())
    query_weight[q] += x

used = set()
dq = deque([1])
used.add(1)
ans = [0] * (N + 1)

while dq:
    node = dq.popleft()
    can = connect_lst[node]

    used.add(node)
    ans[node] += query_weight[node]

    for c in can:
        if c not in used:
            ans[c] += ans[node]
            dq.append(c)


ans = [str(w) for w in ans[1:]]
print(' '.join(ans))
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
while len(l)>=3:
  for j in range(1,len(l)):
    for k in range(j+1,len(l)):
      if l[0]<l[j]+l[k] and l[j]<l[k]+l[0] and l[k]<l[0]+l[j]:
        ans+=1
  del l[0]
print(ans)

### FIXED CODE ###

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

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

times = 0
min_num = N+1
for i in range(len(P)):
  safe = True
  if min_num < int(P[i]):
    continue
  min_num = int(P[i])
  for j in range(i+1):
    if not int(P[i]) <= int(P[j]):
      safe = False
  if safe:
    times += 1
print(times)

### FIXED CODE ###

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

times = 0
min_num = N+1
for i in range(len(P)):
  safe = True
  if min_num < int(P[i]):
    continue
  min_num = int(P[i])
  times += 1
print(times)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = []
for i in range(n):
    s.append(''.join(sorted(input())))
ans = 0
s1 = set(s)
for i in s1:
    n = s.count(i) - 1
    ans += n * (n+1) / 2
print(int(ans))


### FIXED CODE ###

import collections
 
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for si in set(s):
    n = c[si]
    ans += n * (n - 1) // 2
print(ans)