Harryxun/stf_run huggingface dataset:
def main():
    def DFS(v):
        if DP[v] == -1:
            res = 0
            for i in G[v]:
                res = max(res, DFS(i) + 1)

            DP[v] = res
            
        return DP[v]


    N, M = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(M)]

    G = [[] for _ in range(N)]
    for x, y in xy:
        G[x - 1].append(y - 1)

    DP = [-1] * N
    for v in range(N):
        DFS(v)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    xy = [list(map(int, input().split())) for _ in range(M)]

    G = [[] for _ in range(N)]
    ins = [0] * N
    for i in range(M):
        G[xy[i][0] - 1].append(xy[i][1] - 1)
        ins[xy[i][1] - 1] += 1

    DP = [0] * N
    queue = deque()
    for i in range(N):
        if ins[i] == 0:
            queue.append(i)

    while queue:
        v = queue.popleft()
        for i in G[v]:
            ins[i] -= 1
            if ins[i] == 0:
                DP[i] = max(DP[i], DP[v] + 1)
                queue.append(i)

    print(max(DP))


if __name__ == '__main__':
    main()

exit()
x=int(input())
l=[]
for b in range (1,32):
    for i in range (2,10):
        if b**i <=x:
            l.append (b**i)
print(max(l))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if abs(c-a)<= d:
    print('Yes')
elif abs(b-a)<=d and abs(c-b)<=d:
    print('Yes')
else:
    print('No')
N=int(input())
print(len(set(input() for n in range(N)])))

### FIXED CODE ###

N=int(input())
print(len(set([input() for n in range(N)])))
from collections import deque

n = int(input())
s = input()
cp = []
for i, c in enumerate(s):
    if c == 'D':
        cp.append((0, i))
    elif c == 'M':
        cp.append((1, i))
    elif c == 'C':
        cp.append((2, i))

i = 0
while cp[i][0] != 0:
    i += 1
cp = cp[i:]
while cp[-1][0] != 2:
    cp.pop()

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    deq = deque()
    count_a = 0
    rejected_a = 0
    count_internal_b = 0
    sum_internal_b = 0
    for item in cp:
        # print(deq, count_a, rejected_a, count_internal_b, sum_internal_b)
        if item[0] == 0:
            count_a += 1
            deq.append(item)
        elif item[0] == 1:
            count_internal_b += 1
            sum_internal_b += count_a
            deq.append((*item, count_a))
        else:
            left_limit = item[1] - k
            while deq and deq[0][1] <= left_limit:
                old_item = deq.popleft()
                if old_item[0] == 0:
                    rejected_a += 1
                elif old_item[0] == 1:
                    count_internal_b -= 1
                    sum_internal_b -= old_item[2]
            ans += sum_internal_b - rejected_a * count_internal_b
    buf.append(ans)
print('\n'.join(map(str, buf)))


### FIXED CODE ###

from itertools import accumulate

n = int(input())
s = input()
acc_cnt_a = [0] * (n + 1)
acc_cnt_b = [0] * (n + 1)
acc_cnt_ab = [0] * (n + 1)
c_loc = []
cnt_a = 0
for i, c in enumerate(s):
    if c == 'D':
        acc_cnt_a[i] += 1
        cnt_a += 1
    elif c == 'M':
        acc_cnt_b[i] += 1
        acc_cnt_ab[i] += cnt_a
    elif c == 'C':
        c_loc.append(i + 1)
acc_cnt_a = [0] + list(accumulate(acc_cnt_a))
acc_cnt_b = [0] + list(accumulate(acc_cnt_b))
acc_cnt_ab = [0] + list(accumulate(acc_cnt_ab))

q = int(input())
buf = []
for k in map(int, input().split()):
    ans = 0
    for r in c_loc:
        l = r - k
        if l > 0:
            rejected_a = acc_cnt_a[l]
            cnt_internal_b = acc_cnt_b[r] - acc_cnt_b[l]
            cnt_internal_ab = acc_cnt_ab[r] - acc_cnt_ab[l]
            ans += cnt_internal_ab - rejected_a * cnt_internal_b
        else:
            ans += acc_cnt_ab[r]
    buf.append(ans)
print('\n'.join(map(str, buf)))
def compare_cards(a, b):
    return int(a[1]) < int(b[1])

N = int(input())
C = input().split()

bubbleC = C.copy()

#compare_cards(C[0],C[1])
print(*C)

### FIXED CODE ###

def compare_cards(a, b):
    return a[1] < b[1]

def bubble(C):
    for i in range(len(C)):
        for j in range(len(C) - 1, i, -1):
            if compare_cards(C[j], C[j - 1]):
                C[j], C[j - 1] = C[j -1], C[j]

def selection(C):
    for i in range(len(C)):
        mini = i
        for j in range(i, len(C)):
            if compare_cards(C[j], C[mini]):
                mini = j
        C[i], C[mini] = C[mini], C[i]

def check_stable(originC, sortedC):
    for i in range(len(originC) - 1):
        if not compare_cards(sortedC[i], sortedC[i + 1]):
            if originC.index(sortedC[i]) > originC.index(sortedC[i + 1]):
                return 'Not stable'
    return 'Stable'

        
N = int(input())
C = input().split()

bubbleC = list(C)
selectionC = list(C)

bubble(bubbleC)
selection(selectionC)

print(*bubbleC)
print(check_stable(C, bubbleC))
print(*selectionC)
print(check_stable(C, selectionC))
import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}
 
def create_bound(p, K, ub):
	if p - K + 1 >= 0:
		return [(p - K + 1, p + 1)]
	else:
		return [(0, p + 1), ((p - K + 1) % ub, ub)]
 
for i in range(N):
	x, y, c = input().split()
	nx = int(x) % ub
	ny = (int(y) + ADD[c]) % ub
	for add in [0, K]:
		for xlb, xub in create_bound((nx + add) % ub, K, ub):
			for ylb, yub in create_bound((ny + add) % ub, K, ub):
				b[xlb][ylb] += 1
				b[xlb][yub] -= 1
				b[xub][ylb] -= 1
				b[xub][yub] += 1
 
b_arr = np.array(b)
for i in range(ub):
	b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
	b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}

def create_bound(p, K, ub):
	if p - K + 1 >= 0:
		return [(p - K + 1, p + 1)]
	else:
		return [(0, p + 1), ((p - K + 1) % ub, ub)]

for i in range(N):
	x, y, c = input().split()
	nx = int(x) % ub
	ny = (int(y) + ADD[c]) % ub
	for add in [0, K]:
		for xlb, xub in create_bound((nx + add) % ub, K, ub):
			for ylb, yub in create_bound((ny + add) % ub, K, ub):
				b[xlb][ylb] += 1
				b[xlb][yub] -= 1
				b[xub][ylb] -= 1
				b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
	b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
	b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
Submission

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
ub = K * 2
b = [[0 for j in range(ub + 1)] for i in range(ub + 1)]
ADD = {"B": 0, "W": K}


def create_bound(p, K, ub):
    if p - K + 1 >= 0:
        return [(p - K + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - K + 1) % ub, ub)]


for i in range(N):
    x, y, c = input().split()
    nx = int(x) % ub
    ny = (int(y) + ADD[c]) % ub
    for add in [0, K]:
        for xlb, xub in create_bound((nx + add) % ub, K, ub):
            for ylb, yub in create_bound((ny + add) % ub, K, ub):
                b[xlb][ylb] += 1
                b[xlb][yub] -= 1
                b[xub][ylb] -= 1
                b[xub][yub] += 1

b_arr = np.array(b)
for i in range(ub):
    b_arr[i + 1, :] += b_arr[i, :]
for j in range(ub):
    b_arr[:, j + 1] += b_arr[:, j]
print(b_arr.max())
import time
import random
def calc(a) :
    sum = 0
    for i in range(len(a) - 1):
        sum += abs(a[i + 1] - a[i])
    return sum

def crossList(a,b):
    y = []
    if len(a) > len(b):
        for i in range(len(b)):
            y.append(a[i])
            y.append(b[i])
        y.append(a[i+1])
    elif len(a) < len(b): 
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
        y.append(b[i+1])
    else :
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
    return y

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
b = []
c = []
f = []
g = []
if len(a) % 2 == 1:
    b = a[0:int((len(a) - 1)/2) ]
    c = a[int((len(a) - 1)/2) : len(a)]
else :
    b = a[0:int((len(a) )/2)  ]
    c = a[int((len(a) )/2) : len(a)]
c.reverse()
g.reverse()
d = []
e = []
h = []
j = []
forward = True;
for i in range(len(b)):
    if forward:
        d.append(b[i])
    else :
        d.insert(0,b[i])
    forward = not forward
forward = True

for i in range(len(c)):
    if forward:
        e.append(c[i])
    else :
        e.insert(0,c[i])
    forward = not forward
forward = True
h = d[:]
j = e[:]
if (len(h) % 2 == 0) :
    h.append(j.pop(-1))
else:
    h.insert(0,j.pop(0))

print(max(calc(crossList(d,e)),calc(crossList(d[::-1],e[::-1])),
          calc(crossList(d,e[::-1])),calc(crossList(d[::-1],e)),
          calc(crossList(h[::-1],j[::-1])),calc(crossList(h,j[::-1])),
          calc(crossList(h[::-1],j)),calc(crossList(h,j))))



### FIXED CODE ###

import time
import random
def calc(a) :
    sum = 0
    for i in range(len(a) - 1):
        sum += abs(a[i + 1] - a[i])
    return sum

def crossList(a,b):
    y = []
    if len(a) > len(b):
        for i in range(len(b)):
            y.append(a[i])
            y.append(b[i])
        y.append(a[i+1])
    elif len(a) < len(b): 
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
        y.append(b[i+1])
    else :
        for i in range(len(a)):
            y.append(b[i])
            y.append(a[i])
    return y

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort()
b = []
c = []
if len(a) % 2 == 1:
    b = a[0:int((len(a) - 1)/2) ]
    c = a[int((len(a) - 1)/2) : len(a)]
else :
    b = a[0:int((len(a) )/2)  ]
    c = a[int((len(a) )/2) : len(a)]
c.reverse()
d = []
e = []
forward = True;
for i in range(len(b)):
    if forward:
        d.append(b[i])
    else :
        d.insert(0,b[i])
    forward = not forward
forward = True

for i in range(len(c)):
    if forward:
        e.append(c[i])
    else :
        e.insert(0,c[i])
    forward = not forward

h = d[:]
j = e[:]
if len(a) % 2 == 1:
    if (len(h) % 2 == 0) :
        h.append(j.pop(-1))
    else:
        h.insert(0,j.pop(0))

print(max(calc(crossList(d,e)),calc(crossList(d[::-1],e[::-1])),
          calc(crossList(d,e[::-1])),calc(crossList(d[::-1],e)),
          calc(crossList(h[::-1],j[::-1])),calc(crossList(h,j[::-1])),
          calc(crossList(h[::-1],j)),calc(crossList(h,j))))
def f(x):
    length=0
    array=[]
    for b in x:
        if b==True:
            length+=1
        else:
            array.append(length)
            length=0

    return array

s=input()
sb = ['A','C','G','T']
boola=list()
length=0

for x in s:
    boola.append(x in sb)

print(max(f(boola)))
    

### FIXED CODE ###

def f(x):
    length=0
    array=[]
    for b in x:
        if b==True:
            length+=1
        else:
            array.append(length)
            length=0

    array.append(length)
    return array

s=input()
sb = ['A','C','G','T']
boola=list()
length=0

for x in s:
    boola.append(x in sb)

print(max(f(boola)))
n = int(input())
d  =list(map(int,input().split()))
d.sort()
m = int(input())
t = list(map(int,input().split()))
t.sort()
for x in t:
    while d[i] < x:
        i += 1
    if d[i] == x:
        i += 1
    else:
        print("NO")
        exit()
print("YES")

### FIXED CODE ###

from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

input()
d = Counter(map(int,input().split()))
input()
t = Counter(map(int,input().split()))
d.subtract(t)
if -d:
    print("NO")
else:
    print("YES")
from math import ceil
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
for i in range(ceil(pow(P,1/N)),0,-1):
    if P%pow(i,N)==0:
        print(i)
        break

### FIXED CODE ###

from collections import Counter
N,P =map(int,input().split(' '))
if N==1:
    print(P)
    exit()
prime = []
f = 2
while f**2 <=P:
    if P%f==0:
        prime.append(f)
        P//=f
    else:
        f += 1
if P != 1:
    prime.append(f)

ans = 1
for k,v in Counter(prime).items():
    if v//N:
        ans *= k**(v//N)
print(ans)
import sys
from functools import lru_cache

sys.setrecursionlimit(10000)

INF = 10**9+7

@lru_cache(maxsize=1000)
def c(n,k):
    return 1 if (k<=0 or n<=k) else (c(n-1,k-1)+c(n-1,k))%INF

# for i in range(5):
#     print([c(i, j) for j in range(i+1)])

def solver(x, y):
    if (x, y) == (0, 0):
        return 0
    if (x+y)%3 != 0:
        return 0
    k = (x+y)//3
    (xi, yi) = (k, 2*k)
    for i in range(k+1):
        if (xi, yi) == (x, y):
            return c(k, i)
        else:
            (xi, yi) = (xi+1, yi-1)
    return 0

x, y = map(int, input().split())
res = solver(x, y)
print(res)

### FIXED CODE ###

import sys

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def comb_num_mod(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

def solver(x, y):


    if (x, y) == (0, 0):
        return 0
    if (x+y)%3 != 0:
        return 0
    k = (x+y)//3
    (xi, yi) = (k, 2*k)
    for i in range(k+1):
        if (xi, yi) == (x, y):
            return comb_num_mod(k, i) 
        else:
            (xi, yi) = (xi+1, yi-1)
    return 0

x, y = map(int, input().split())
res = solver(x, y)
print(res)
import collections
n=int(input())
lst=[int(input()) for i in range(n)]
xs=list(set(lst))
ans=0
lst=collections.Counter(lst)
for i in xs:
  if lst[i]%=1:
    ans+=1

print(ans)

### FIXED CODE ###

import collections
n=int(input())
lst=[int(input()) for i in range(n)]
xs=list(set(lst))
ans=0
lst=collections.Counter(lst)
for i in xs:
  if lst[i]%2==1:
    ans+=1

print(ans)
a=int(input())
b=0
for i in range(9):
  for k in range(9):
    if (i+1)*(k+1)==a:
      print("Yes")
      break
      b=b+1
if b=81:
  print("No")

### FIXED CODE ###

a=int(input())
if a==11 or a==13 or a==17 or a==19 or a==22 or a==23 or a==26 or a==29 or a==31 or a==33 or a==34 or a==37 or a==38 or a==39 or a==41 or a==43 or a==44 or a==46 or a==47 or a==50 or a==51 or a==52 or a==53 or a==55 or a==57 or a==58 or a==59 or a==60 or a==61 or a==62 or a==65 or a==66 or a==67 or a==68 or a==69 or a==70 or a==71 or a==73 or a==74 or a==75 or a==76 or a==77 or a==78 or a==79 or a==80 or a>=82:
  print("No")
else:
  print("Yes")
n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

one_mod = 0
zero_mod = 0
for b in x:
    one_mod = (one_mod*2 + int(b)) % one_popcnt
    zero_mod = (zero_mod*2 + int(b)) % zero_popcnt

f = [0]*220000
popcnt = [0]*220000
for i in range(1, 220000):
    popcnt[i] = popcnt[i//2] + i % 2
    f[i] = f[i % popcnt[i]] + 1

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        nxt = one_mod
        nxt -= pow(2, i, one_popcnt)
        nxt %= one_popcnt
        print(f[nxt]+1)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += pow(2, i, zero_popcnt)
        nxt %= zero_popcnt
        print(f[nxt]+1)


### FIXED CODE ###

n = int(input())
x = input()
x_popcnt = x.count('1')
one_popcnt = x_popcnt - 1
zero_popcnt = x_popcnt + 1

one_mod = 0
zero_mod = 0
for b in x:
    if one_popcnt != 0:
        one_mod = (one_mod*2 + int(b)) % one_popcnt
    zero_mod = (zero_mod*2 + int(b)) % zero_popcnt

f = [0]*220000
popcnt = [0]*220000
for i in range(1, 220000):
    popcnt[i] = popcnt[i//2] + i % 2
    f[i] = f[i % popcnt[i]] + 1

for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_popcnt != 0:
            nxt = one_mod
            nxt -= pow(2, i, one_popcnt)
            nxt %= one_popcnt
            print(f[nxt]+1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += pow(2, i, zero_popcnt)
        nxt %= zero_popcnt
        print(f[nxt]+1)
n = int(input())
l = input().split()
lst = list(map(int,l))

sum = 0
j = 1
for i in lst:
    sum += (i-j)
    j+=1

//四捨五入
b = round(sum/n)

#print(b)

j = 1
sad = 0
for a in lst:
    sad += abs(a-(b+j))
    j += 1
print(sad)

### FIXED CODE ###

n = int(input())
l = input().split()
lst = list(map(int,l))
x = []

for i in range(n):
    x.append(0)
    x[i] = lst[i] - (i+1)

#print(x)
x.sort()
#print(x)

b = x[n//2]

#print(b)

sad = 0

#print(lst)

for i in range(n):
    sad += abs(lst[i]-b-i-1)

print(sad)
import sys

stdin = sys.stdin

ns = lambda : stdin.readline().rstrip()
na = lambda : map(int, stdin.readline().split())
ni = lambda : int(ns())
def main():
  n = ni()
  nagasa = lambda x: len(str(x))
  def f(a, b):
    x = nagasa(a)
    y = nagasa(b)
    return x if x > y else y

  def divi(n):
    res = []
    for i in range(1, int(n**0.5)+1):
      if n % i == 0:
        res.append(i)
        if i != n // i:
          res.append(n // i)
    return res
  x = divi(n)
  print(f(x[-1], x[-2]))

main()

### FIXED CODE ###

N = int(input())
x = round(N**0.5)
while N%x != 0:
  x -= 1
print(len(str(N//x)))
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
  

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

for i in range(1,k+1):
  #青をi個に分ける(最低数(i-1個)の赤で)
  a=comb(k-1, i-1, 10**9+7)
  #赤の残りは(n-k)-(i-1)こ
  #これをいいかんじにならべる
  b=comb(n-k+1, i, 10**9+7)
  print(a,b,(a*b)%p)


### FIXED CODE ###

def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
  

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

for i in range(1,k+1):
  #青をi個に分ける(最低数(i-1個)の赤で)
  a=comb(k-1, i-1, 10**9+7)
  #赤の残りは(n-k)-(i-1)こ
  #これをいいかんじにならべる
  b=comb(n-k+1, i, 10**9+7)
  print((a*b)%(10**9+7))
S=list(input())
k=int(input())

cnt,ans=0,0
for i in range(1,len(S)):
  if S[i-1]==S[i]:
    cnt+=1
  else:
    cnt+=1
    ans+=cnt//2
    cnt=0
ans+=cnt//2
if S[0]==S[-1] and S[-1]==S[-2]:
  print(ans*k+k)
else:
  print(ans*k)

### FIXED CODE ###

S=list(input())
k=int(input())

cnt,ans=0,0
T=S+S
for i in range(1,len(T)):
  if T[i-1]==T[i]:
    cnt+=1
  else:
    ans+=(cnt+1)//2
    cnt=0
  if i==len(S)-1:
    ans+=(cnt+1)//2
    tmp=ans

if len(S)==1:
  print(k//2)
  exit()
if len(S)==2:
  if S[0]==S[1]:
    print(k)
  else:
    print(0)
  exit()
  
if len(set(T))==1:
  if len(S)%2==0:
    print(len(S)//2*k)
  else:
    out=(len(S)//2)*(k-(k//2))+(len(S)//2+1)*(k//2)
    print(out)
  exit()
      
print(tmp+(ans-tmp)*(k-1))
a,b,c,d=(int(i) for i in input().split(' '))
print(min(a,b)+min(c,d))

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
print(min(a,b)+min(c,d))
import sys
#import cython

def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    A, B, C, K = map(int,read().split())
    t = [1]*A+[0]*B+[-1]*C
    print(sum(t[:K]))
    #a, b, c = map(int,read().split())
    #l = [int(read()) for _ in range(5)]
    

 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#import cython

def main():
    read = lambda: sys.stdin.readline().rstrip()
    
    #N: cython.longlong = 0
    A, B, C, K = map(int,read().split())
    print(K if A >= K else A if K-A <= B else A-(K-A-B))
    #a, b, c = map(int,read().split())
    #l = [int(read()) for _ in range(5)]
    

 
if __name__ == "__main__":
    main()
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
A.append((0, 0))

ans = [0] * N
now = float('inf')

for j, (a, i) in enumerate(A[:N], start=1):
    now = min(now, a)
    ans[now] += j * (now - A[j][0])

print(*ans, sep='\n')


### FIXED CODE ###

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

ans = [0] * N

numList = [(a, i) for i, a in enumerate(A)]
numList.sort(reverse=True)
numList.append((0, 0))

y = float('inf')
for c, (a, i) in enumerate(numList[: N], start=1):
    y = min(y, i)
    ans[y] += c * (a - numList[c][0])

print(*ans, sep='\n')
s=input()
 l=['SUN','MON','TUE','WED','THU','FRI','SAT']
 l.reverse()
 print(l.index(s)+1)

### FIXED CODE ###

s=input()
l=['SUN','MON','TUE','WED','THU','FRI','SAT']
l.reverse()
print(l.index(s)+1)
n,r = int(input())
if n>10:
  print(r)
else:
  print(r-(100*(10-n)))

### FIXED CODE ###

n,r = map(int,input().split())
if n>10:
  print(r)
else:
  print(r+100*(10-n))
import collections

bluecard = []
redcard = []

n = int(input())
for i in range(n):
    bluecard.append(input())

m = int(input())
for i in range(m):
    redcard.append(input())

blue_count = collections.Counter(bluecard)
red_count = collections.Counter(redcard)
diff = red_count - blue_count
print(diff.most_common(1)[0][1])



### FIXED CODE ###

import collections

bluecard = []
redcard = []

n = int(input())
for i in range(n):
    bluecard.append(input())

m = int(input())
for i in range(m):
    redcard.append(input())

blue_count = collections.Counter(bluecard)
red_count = collections.Counter(redcard)
diff = blue_count - red_count
if len(diff.keys()) > 0:
    print(diff.most_common(1)[0][1])
else:
    print(0)
S,T = open(0)
Snum = len(S)

if S = T[:Snum]:
  print("Yes")
  
else:
  primt("No")

### FIXED CODE ###

S = str(input())
T = str(input())

if T.startswith(S):
  print("Yes")
else:
  print("No")
x,y = input().split()
l = [A,B,C,D,E,F]
if l.index(x) < l.index(y):
  print("<")
elif l.index(x) > l.index(y):
  print(">")
else:
  print("=")

### FIXED CODE ###

x,y = input().split()
if x == "A":
  if y == "A":
    print("=")
  else:
    print("<")
elif x == "B":
  if y == "A":
    print(">")
  elif y == "B":
    print("=")
  else:
    print("<")
elif x == "C":
  if y == "A" or y == "B":
    print(">")
  elif y == "C":
    print("=")
  else:
    print("<")
elif x == "D":
  if y == "E" or y == "F":
    print("<")
  elif y == "D":
    print("=")
  else:
    print(">")
elif x == "E":
  if y == "F":
    print("<")
  elif y == "E":
    print("=")
  else:
    print(">")
else:
  if y == "F":
    print("=")
  else:
    print(">")
# import itertools
# import math
import numpy as np


H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort()

ans = 0
dp = np.zeros(H, dtype=int)
for a, b in AB:
    ans = max(ans, dp.max() + b)
    np.max(dp[:-a] + b, dp[a:], out=dp[a:])

print(ans)


### FIXED CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(1000000)

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

AB = []
for i in range(N):
    A, B = map(int, input().split())
    AB.append((A, B))

AB.sort(key=lambda ab: (ab[0] / ab[1], -ab[0]), reverse=True)


@lru_cache(maxsize=None)
def solve(h):
    if h <= 0:
        return 0
    best = float("inf")
    for a, b in AB:
        val = b + solve(h - a)
        if val < best:
            best = val
        else:
            break
    return best


print(solve(H))