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

N = int(input())
A = [0]*N
B = [0]*N

for i in range(N):
    A[i] = int(input())


for i in range(N):
    for j in range(N):
        if j != i:
            B[j] = A[j]
        else:
            B[j] = 0
    print(max(B))

### FIXED CODE ###

N = int(input())
A = [0]*N

for i in range(N):
    A[i] = int(input())

mx = max(A)
mxi = A.index(max(A))

for i in range(N):
    if i != mxi:
        print(mx)
    elif i == 0:
        print(max(A[1:N]))
    elif i == N-1:
        print(max(A[0:N-1]))
    else:
        print(max(max(A[0:i]),max(A[i+1:N])))
### BUGGY CODE ###

N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[100001 for i in range(N+1)]]

for i in range(N):
  dis.append([100001 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)




for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])

def permutList(l):
    if not l:
            return [[]]
    res = []
    for e in l:
            temp = l[:]
            temp.remove(e)
            res.extend([[e] + r for r in permutList(temp)])

    return res

N=permutList(r)

mini=100000000000
for i in N:
  p=0
  for j in range(0,len(i)-1):
    p+=dis[i[j]][i[j+1]]
  mini=min(p,mini)
print(mini)

### FIXED CODE ###

N,M,C=[int(x) for x in str(input()).split()]
r=[int(x) for x in str(input()).split()]
ABC=[[0 for i in range(4)]]

dis=[[1000000000000 for i in range(N+1)]]

for i in range(N):
  dis.append([1000000000000 for i in range(N+1)])


for i in range(M):
  x=[0]+[int(x) for x in str(input()).split()]
  ABC.append(x)
  dis[x[1]][x[2]]=x[3]
  dis[x[2]][x[1]]=x[3]
  y=[0,x[2],x[1],x[3]]
  ABC.append(y)

for i in range(1,N+1):
  dis[i][i]=0


for k in range(1,N+1):
  for i in range(1,N+1):
    for j in range(1,N+1):
      dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])


mi=1000000000000
def perm(a,i):
  global mi
  if i==len(a):      

    p=0
    for x in range(len(a)-1):
      p+=dis[a[x]][a[x+1]]

    mi=min(mi,p)


  else:
    for j in range(i,len(a)):
      a[i],a[j]=a[j],a[i]
      perm(a,i+1)
      a[i],a[j]=a[j],a[i]


perm(r,0)

print(mi)
### BUGGY CODE ###

from sys import stdin, setrecursionlimit
from collections import Counter, deque, defaultdict
import heapq
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    Ch, Cw = Ch - 1, Cw - 1
    Dh, Dw = Dh - 1, Dw - 1
    S = [list(input()) for _ in range(H)]
    counter = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                counter += 1
    # for row in S: print(*row)

    # DFSする (近隣への移動はコスト0，ワープ(5x5-grid)はコスト1)
    dist = defaultdict(lambda: float("inf"))
    dist[Ch, Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        if (h, w) == (Dh, Dw):
            break

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                if dist[nh, nw] == float("inf") or dist[nh, nw] > dist[h, w]:
                    dist[nh, nw] = dist[h, w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] != '#':
                    if dist[nh, nw] == float("inf"):
                        if dist[nh, nw] > dist[h, w] + 1:
                            dist[nh, nw] = dist[h, w] + 1
                            queue.append((nh, nw))

    if dist[Dh, Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh, Dw])

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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())
    S = [input() for _ in range(H)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

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

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

s = 0
t = 0
while t < n:
  for i in range(a):
    s += 1
    t += 1
    if t == n:
      break
  for j in range(b):
    t += 1
    if t == n:
      break
print(s)

### FIXED CODE ###

n,a,b = map(int, input().split())
x = n // (a+b)
ans = a * x + min(a, n - (a+b) * x)
print(ans)
### BUGGY CODE ###

def calculate(arr,S):

    result = []
    even = 0
    for i in range(len(arr)):

        if i % 2 == 0:
            even = S-calculate2(i+1,arr[i+1:])
            result.append(even)
        else:
            odd = arr[i-1]*2-even
            result.append(odd)
            S = S - even - odd

    return result

def calculate2(i,arr):
    # 取偶数项
    return sum(arr[::2])*2

def calculateTotaAmount(arr):
    return sum(arr)

def printArr(arr):
    result = ""
    for i in range(len(arr)):
        result += str(arr[i]) + " "

    return result



N = int(input())

S = input().split(" ")
aArr = [int(s) for s in S]


result = calculate(aArr,calculateTotaAmount(aArr))

print(" ".join([str(s) for s in result]))



### FIXED CODE ###

def calculate(N, arr, S):
    result = []
    tmp = 0
    for i in range(len(arr)):
        if i % 2 == 1:
            tmp += arr[i] * 2

    x0 = S - tmp

    result.append(x0)

    for i in range(1, N):
        result.append(arr[i - 1] * 2 - result[i - 1])

    return result


def calculate2(i, arr):
    # 取偶数项
    return sum(arr[::2]) * 2


def calculateTotaAmount(arr):
    return sum(arr)


def printArr(arr):
    result = ""
    for i in range(len(arr)):
        result += str(arr[i]) + " "

    return result



N = int(input())

S = input().split(" ")
aArr = [int(s) for s in S]

result = calculate(N, aArr, calculateTotaAmount(aArr))
print(" ".join([str(s) for s in result]))
### BUGGY CODE ###

print(min(eval('eval(input().replace(" ","+")),'*int(input()))))

### FIXED CODE ###

n,*t=map(int,open(0).read().split());print(sum(sorted(zip(t[::2],t[1::2]))[-1]))
### BUGGY CODE ###

k = int(input())
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))
cnt = 0
l = []
for i in range(1, k + 1):
    for j in range(1, k + 1):
        
        l.append(gcd(i, j))
for h in range(1, k + 1):
    for p in l:
        cnt += gcd(h, p)
print(cnt)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
k = int(input())
cnt = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        for h in range(1, k + 1):
            cnt += gcd(i, j, h)
print(cnt)
### BUGGY CODE ###

from collections import deque
from itertools import product


def read():
    H, W = list(map(int, input().split()))
    S = ''
    S += ('#' * (W+2))
    for h in range(H):
        buf = input()
        S += '#' + buf + '#'
    S += ('#' * (W+2))
    return H, W, S


def bfs(yx, H, W, S):
    dirs = [1, W+2, -1, -W-2]
    visited = [False] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while len(q) > 0:
        yx, depth = q.popleft()
        visited[yx] = True
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and not visited[nyx]:
                q.append((nyx, depth+1))
    return max_depth


def solve(H, W, S):
    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

import sys

input = sys.stdin.readline


def main():
    N, W = map(int, input().split())
    dp = [0] * (W + 1)

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

    for w, v in WV:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)

    print(dp[-1])


main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    N, W = map(int, input().split())
    dp = [0] * (W + 1)

    WV = (map(int, input().split()) for _ in range(N))

    for w, v in WV:
        for j in range(W, w - 1, -1):
            tmp = dp[j - w] + v
            if tmp > dp[j]:
                dp[j] = tmp

    print(dp[-1])


main()
### BUGGY CODE ###

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

ans = 0

for i in range(min(a), max(a)+1):
    cnt = 0
    for j in range(n):
        if abs(a[j]-i) <= 1:
            cnt += 1
    if cnt > 0:
        ans = max(ans, cnt)

print(ans)

### FIXED CODE ###

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

d = [0] * (10**5)

for i in range(n):
    d[a[i]] += 1

ans = 1

for j in range(1, n-1):
    ans = max(ans, d[j-1] + d[j] + d[j+1])

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

N, M = map(int, input().split())
A = [ input().split() for i in range(M)]
cac = 0
cwa = 0

for i in range(1, N+1):
  list1 = []
  for j in range(M):
    if  A[j][0] == str(i):
      list1.append(A[j][1])

  
  for k in range(1, len(list1)):
    if list1[k]=='AC':
      cac += 1
      cwa += list1[:k].count('WA')
      break
print(cac, cwa)

### FIXED CODE ###

n, m = map(int, input().split())
a = [input().split() for i in range(m)]
wa =[0]*n #ACまでのWA数
ac = [0]*n

for i in range(m):
    if a[i][1] == 'AC':
      ac[int(a[i][0])-1] = 1
    else:
      if ac[int(a[i][0])-1]==0:
        wa[int(a[i][0])-1] +=1
cnt1, cnt2= 0,0
for i in range(n):
  if ac[i] ==1:
    cnt1 += ac[i]
    cnt2 += wa[i]
        
print(cnt1, cnt2)
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline


#readline = open('???.txt').readline

def main():
    v, e = map(int, readline().split())
    residual_flow = [[0] * v for _ in range(v)]
    g = defaultdict(list)
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c:
            g[s].append(t)
            residual_flow[s][t] = c

    while True:
        route, flow = search(g, residual_flow, source, sink)
        if route is None:
            break
        for i in range(1, len(route)):
            residual_flow[route[i - 1]][route[i]] -= flow
            residual_flow[route[i]][route[i - 1]] += flow

    print(sum(residual_flow[i][source] for i in g[source]))

def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v in route:
                continue
            next_flow = min(residual[u][v], flow)
            if 0 < next_flow:
                dfs_stack.append((v, u, next_flow))
    return None, None
main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict
readline = stdin.readline


def main():
    v, e = map(int, readline().split())
    g = defaultdict(set)
    residual = [[0] * v for _ in range(v)]
    source, sink = 0, v - 1

    for _ in range(e):
        s, t, c = map(int, readline().split())
        if 0 < c and s != sink and t != source:
            g[s] |= {t}
            g[t] |= {s}
            residual[s][t] = c

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow

    print(sum(residual[sink][i] for i in g[sink]))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()
### BUGGY CODE ###

import sys
from collections import namedtuple
from heapq import heappush, heappop

INF = sys.maxsize

P = namedtuple('P', 'cost v')
Edge = namedtuple('Edge', 'cost to')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

G = [[] for _ in range(N)]
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  y1, c = yg[i]
  y2, d = yg[i + 1]
  G[a].append(Edge(abs(x1 - x2), b))
  G[b].append(Edge(abs(x1 - x2), a))
  G[c].append(Edge(abs(y1 - y2), d))
  G[d].append(Edge(abs(y1 - y2), c))

total = 0
costs = [INF] * N
costs[0] = 0  # 集合Xからの最短距離
used = set()

q = [P(0, 0)]

while q: 
  p = heappop(q)

  if len(used) >= N:
    break

  if p.v in used and p.cost >= costs[p.v]:
    continue

  costs[p.v] = 0
  total += p.cost
  used.add(p.v)

  for cost, to in G[p.v]:
    if costs[to] > costs[p.v] + cost:
      costs[to] = costs[p.v] + cost
      heappush(q, P(costs[to], to))

print(total)


### FIXED CODE ###

from collections import namedtuple


class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n + 1)]
    self.size = [1] * (n + 1)

  def is_same(self, a, b):
    return self.find(a) == self.find(b)

  def unite(self, a, b):
    a = self.find(a)
    b = self.find(b)  
    if self.size[a] < self.size[b]:
      a, b = b, a
    self.par[b] = a
    self.size[a] += self.size[b]

  def size_of(self, a):
    return self.size[self.find(a)]

  def find(self, a):
    if a == self.par[a]:
      return a
    self.par[a] = self.find(self.par[a])
    return self.par[a]

Edge = namedtuple('Edge', 'w s t')
X = namedtuple('X', 'x i')
Y = namedtuple('Y', 'y i')

N = int(input())

edges = []
xg = []
yg = []

for i in range(N):
  x, y = map(int, input().split())
  xg.append(X(x, i))
  yg.append(Y(y, i))

xg.sort()
yg.sort()

for i in range(N - 1):
  x1, a = xg[i]
  x2, b = xg[i + 1]
  edges.append(Edge(abs(x1 - x2), a, b))

for i in range(N - 1):
  y1, a = yg[i]
  y2, b = yg[i + 1]
  edges.append(Edge(abs(y1 - y2), a, b))

edges.sort()

u = UnionFind(N)
cost = 0

for w, s, t in edges:
  if u.is_same(s, t):
    continue
  u.unite(s, t)
  cost += w

print(cost)
### BUGGY CODE ###

import numpy as np
h,w,m = map(int,input().split())
bombX = [0]*h
bombY = [0]*w
bomb = []
for i in range(m):
    i,j = map(lambda x:int(x)-1, input().split())
    bomb.append((i,j))
    bombX[i] += 1
    bombY[j] += 1
maxX = max(bombX)
maxY = max(bombY)
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) not in bomb:
            print(maxX+maxY)
            exit()
print(maxX+maxY-1)


### FIXED CODE ###

h,w,m = map(int,input().split())
bombX = [0]*h
bombY = [0]*w
bomb = set()
maxX = maxY = 0
for i in range(m):
    i,j = map(lambda x:int(x)-1, input().split())
    bomb.add((i,j))
    bombX[i] += 1
    bombY[j] += 1
    maxX = max(maxX,bombX[i])
    maxY = max(maxY,bombY[j])
maxX_index = list(i for i in range(h) if bombX[i] == maxX)
maxY_index = list(i for i in range(w) if bombY[i] == maxY)
for i in maxX_index:
    for j in maxY_index:
        if (i,j) in bomb: continue
        print(maxX+maxY)
        exit()
print(maxX+maxY-1)
### BUGGY CODE ###

N = int(input())

ans = 0

for c in range(1,N,1):
    for a in range(1,N,1):
        b = (N-c)/a
        if b > 0 and  b.is_integer() == True:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())

ans = 0

for a in range(1,N,1):
    ans = ans + (N-1)//a

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

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

### FIXED CODE ###

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

import sys
input = sys.stdin.readline

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans

if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
gate=[0]*n
for i in range(m):
    l,r=map(int,input().split())
    for k in range(l-1,r):
        gate[k]+=1
print(gate.count(m))

### FIXED CODE ###

n,m=map(int,input().split())
card=[]
L=1
R=n
for i in range(m):
    card.append([int(i) for i in input().split()])
for j in card:
    if j[0]<=R:
        if L<=j[0]:
            L=j[0]
            
    else:
        print(0)
        quit()
    if L<=j[1]:
        if j[1]<=R:
            R=j[1]
            
    else:
        print(0)
        quit()
print(R-L+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

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

nodes = [[] for _ in range(N)]
values = [0 for _ in range(N)]

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

for _ in range(Q):
  p, x = map(int, input().split())
  p = p-1
  values[p] += x

def dfs(i, p):
  for c in nodes[i]:
    if c != p:
      values[c] += values[i]
      dfs(c, i)

dfs(0, None)
print(*values)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

nodes = [[] for _ in range(N)]
values = [0 for _ in range(N)]

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

for _ in range(Q):
  p, x = map(int, input().split())
  p = p-1
  values[p] += x

def dfs(i, p):
  for c in nodes[i]:
    if c != p:
      values[c] += values[i]
      dfs(c, i)

dfs(0, None)
print(*values)
### BUGGY CODE ###

nums = list(map(int, input().split(' ')))
k = input()
k = int(k)
i = 0

while i < k:
  maxindex = max(enumerate(nums), key = lambda x:x[1])[0]
  nums[maxindex] *= 2

print(sum(nums))


### FIXED CODE ###

nums = list(map(int, input().split(' ')))
k = input()
k = int(k)
i = 0

while i in range(k):
  maxindex = max(enumerate(nums), key = lambda x:x[1])[0]
  nums[maxindex] *= 2
  i = i + 1

print(sum(nums))
### BUGGY CODE ###

s = input()

count = 0

def str_del(str,index):
    str = str[:index]+str[index+1:]
    return str

def remove_cube(string):
  new_text = string.replace('10', '', 1)
  if new_text == string:
    new_text = string.replace('01', '', 1)
  return new_text

string = s
can_remove = True
while can_remove:
  removed = remove_cube(string)
  if removed != string:
    string = removed
    count += 2
    can_remove = True
  else:
    can_remove = False

print(count)


### FIXED CODE ###

s = input()

count0 = s.count('0')
count1 = s.count('1')
print(min(count0, count1) * 2)
### BUGGY CODE ###

N = int(input())
#2<=N<10**12
a=1
b=1
count=[]
##N=a*b
#output=a+b-2
#積なので対称性よりa<=bとしてオッケー
for i in range(1,N+1):
    if N%i==0:
        a=i
        b=N/i
        if a<=b:
            count.append(int(a+b-2))
print(min(count))


### FIXED CODE ###

N = int(input())
#2<=N<10**12

num=int(N**(1/2)+1)
count=N+1-2
##N=a*b
#output=a+b-2
#積なので対称性よりa<=bとしてオッケー
for i in range(1,num):
    if N%i==0:
       count=min(count,i+N//i -2)
print(count)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [None for _ in range(n+1)]
    bb = [None for _ in range(n+1)]
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    import math
    h,n = map(int, input().split())
    aa = [0]*(n+1)
    bb = [0]*(n+1)
    mp = [[None for _ in range(n+1)] for _ in range(h+1)]
    # 体力i 技の種類j
    for j in range(1, n+1):
      mp[0][j] = 0
      aa[j], bb[j] = map(int, input().split())
    for i in range(1, h+1):
        mp[i][0] = float("inf")
    for j in range(1, n+1):
        for i in range(1, h+1):
        	mp[i][j] = min(mp[i][j-1], mp[max(0, i - aa[j])][j] + bb[j])
    print(mp[h][n])

if __name__ == '__main__':
    main()