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

import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())


def main():
    N = next(read)
    A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
    day = 0

    while True:
        done = set()
        for i in range(1, N + 1):
            if i not in done and A[i]:
                if A[A[i][0]][0] == i and A[i][0] not in done:
                    done.add(A[A[i][0]].popleft())
                    done.add(A[i].popleft())

        if len(done) == 0:
            for i in A:
                if len(i) > 0:
                    print(-1)
                    exit()
            else:
                print(day)
                exit()

        day += 1


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played = set()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        exit()
else:
    print(days)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
S = input()
A = list(digits)

ans = 0
for x in product(A, repeat=3):
	i = 0
	for y in S:
		if y == x[i]:
			if i == 2:
				ans += 1
				break
			else:
				i += 1

print(ans)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
S = input()
A = list(digits)

ans = 0
for x in product(A, repeat=3):
	i = 0
	for y in S:
		if y == x[i]:
			if i == 2:
				ans += 1
				break
			else:
				i += 1

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

n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
query = list(map(int, input().split()))

def solve(i, m):
    if m == 0:
        return True
    elif i >= n or m < A[i]:
        return False
    else:
        return solve(i + 1, m) or solve(i + 1, m - A[i])

for m in query:
    if solve(0, m):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

n = int(input())
A = sorted(list(map(int, input().split())))
q = int(input())
query = list(map(int, input().split()))

@lru_cache(maxsize=None)
def solve(i, m):
    if m == 0:
        return True
    elif i >= n or m < A[i]:
        return False
    else:
        return solve(i + 1, m - A[i]) or solve(i + 1, m)

for m in query:
    if solve(0, m):
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

import sys,collections as cl,bisect as bs,copy
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def s(x):
    a = []
    aa = x[i]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

h,w = m()

a = []
aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    a.append(k)
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[c-1][v]):
                aa[c-1][v] = min(aa[c][v]+1,aa[c-1][v])
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] != min(aa[c][v]+1,aa[c+1][v]):
                aa[c+1][v] = min(aa[c][v]+1,aa[c+1][v])
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] != min(aa[c][v]+1,aa[c][v-1]):
                aa[c][v-1] = min(aa[c][v]+1,aa[c][v-1])
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] != min(aa[c][v]+1,aa[c][v+1]):
                aa[c][v+1] = min(aa[c][v]+1,aa[c][v+1])
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
        




### FIXED CODE ###

import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa[i]
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
### BUGGY CODE ###

from copy import copy

import numpy as np


def main():
    for _ in range(M):
        A2 = A.copy()
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    main()

### FIXED CODE ###

import heapq


def main():
    for _ in range(M):
        mx = heapq.heappop(A) * -1 // 2 * -1
        heapq.heappush(A, mx)

    print(sum(A) * -1)


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(x) * -1 for x in input().split()]
    heapq.heapify(A)
    main()
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
L = LI()
# L = np.array(_L)
#C = np.zeros(N + 1)

# def test(a,b,c):
#     if a<b+c and b<c+a and c<a+b:
#         return True
#     return False

# count = 0
# for pair in itertools.combinations(L, 3):
#     # print(pair)
#     if test(*pair):
#         count += 1
# print(count)

# for i in range(N):
#     for j in range(i+1,N):

from numba import njit
 
# @njit
def f(A):
  count = 0
  for i in range(N):
    for j in range(i + 1, N):
      for k in range(j + 1, N):
        count += (A[k] < A[i] + A[j])
  return count
 
A = np.array(L)
A.sort()
print(f(A))        


### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
L = LI()
# L = np.array(_L)
#C = np.zeros(N + 1)

# def test(a,b,c):
#     if a<b+c and b<c+a and c<a+b:
#         return True
#     return False

# count = 0
# for pair in itertools.combinations(L, 3):
#     # print(pair)
#     if test(*pair):
#         count += 1
# print(count)

# for i in range(N):
#     for j in range(i+1,N):

from numba import njit
 
@njit
def f(A):
  count = 0
  for i in range(N):
    for j in range(i + 1, N):
      for k in range(j + 1, N):
        count += (A[k] < A[i] + A[j])
  return count
 
A = np.array(L)
A.sort()
print(f(A))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
cnt = 0
ans = 0

for i in range(N - 1):

    for j in range(i, N - 1):

        if H[j] >= H[j + 1]:
            cnt += 1
        else:
            break

    # print(i, cnt)
    ans = max(ans, cnt)
    cnt = 0

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        cnt += 1
    else:
        ans.append(cnt)
        cnt = 0

ans.append(cnt)
print(max(ans))
### BUGGY CODE ###

def lcs(s, t):
    n = len(s)
    m = len(t)
    # dp[i][j] := 0-indexでsのi-1文字目までとtのj-1文字目までとのlcsの長さ
    # dp[0][0]は空文字を見ていると考えるからdp[0][0] = 0
    # dp[n][m] := sのn-1文字目まで（0-indexなのでsの末尾）とtのm-1文字目まで(0-indexなのでtの末尾)
    dp = [[0]*(m+1) for _ in range(n+1)]

    for i in range(n):
        for j in range(m):
            # 0-indexでsのi文字目とtのj文字目が等しいなら斜めに移動する
            if s[i] == t[j]:
                dp[i+1][j+1] = dp[i][j] + 1
            # 異なるなら左または上のmaxをとる
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
    res = ""
    while n != 0 and m != 0:  # どちらかが0になったら終わり，dp[0][*]及びdp[*][0]は必ず0なので
        # 上から遷移している場合，nをデクリメントしてよい
        if dp[n][m] == dp[n-1][m]:
            n -= 1
        # 左から遷移している場合，mをデクリメントしてよい
        elif dp[n][m] == dp[n][m-1]:
            m -= 1
        # 左でも上でもなく，左上からの遷移の場合，共通文字
        else:
            n -= 1
            m -= 1
            # 後ろから復元しているので以下のようにする
            res = s[n] + res
    return res


S = input()
T = input()
print(lcs(S, T))


### FIXED CODE ###

s = input()
t = input()

# dp = np.zeros(shape=(len(s), len(t)), dtype=np.int64)
dp = [[0] * (len(t)+1) for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        else:
            dp[i+1][j+1] = max(dp[i+1][j+1], max(dp[i][j+1], dp[i+1][j]))

# print(dp[len(s)][len(t)])


i = len(s)
j = len(t)
# print(type(i))
# print(type(j))
ans = ""
while (i > 0) and (j > 0):
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        ans += s[i-1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

n=int(input())
s=[""]*n
for ii in range(n):
  s[ii]=input()
ss=list(set(s))
#print(ss)
#print(s)
r=[]
for ii in range(len(ss)):
  l=[1 if x==ss[ii] else 0 for x in s]
  r.append([n-sum(l),ss[ii]])
r.sort()
#pint(r)
for ii in range(len(ss)):
  if r[ii][0]==r[0][0]:
    print(r[ii][1])
  else:
    exit()

### FIXED CODE ###

n=int(input())
ss=set()
d=dict()
for ii in range(n):
  s=input()
  if s in ss:
    d[s]+=1
  else:
    ss.add(s)
    d[s]=1
ss=list(ss)
ss.sort()
mx=max(d.values())
for ii in ss:
  if d[ii]==mx:
    print(ii)
### BUGGY CODE ###

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

count = 1
for i in range(1, N):
    if(P[1] <= P[0]):
        P.pop(0)
        count += 1
    else:
        P.pop(1)

print(count)


### FIXED CODE ###

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

count = 1
d = P[0]
for i in range(N - 1):
    if (d > P[i + 1]):
        d = min(P[i], P[i + 1])
        count += 1

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

n = int(input())
nums = input().split()
ans = []
for num in nums:
    ans.append(num)
    ans = ans[::-1]
print(" ".join(ans))

### FIXED CODE ###

def main():
    n = int(input())
    a = input().split()
    if n%2: ans = a[n-1::-2] + a[1:n-1:2]
    else: ans = a[n-1:0:-2] + a[0:n-1:2]
    print(" ".join(ans))
if __name__=="__main__": main()
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]


L = [0]*61

for i in range(N):
    b = bin(A[i])
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

ans = 0
mod = 10**9+7

for i in range(61):
    c = 2**i*(L[i]*(N-L[i]))
    ans += c
    ans %= mod
    
print(ans)

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]


L = [0]*61

for i in range(N):
    b = bin(A[i])
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

ans = 0
mod = 10**9+7

for i in range(61):
    c = 2**i*(L[i]*(N-L[i]))
    ans += c
    ans %= mod
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)


N, Q = map(int, input().split())
G = [[] for _ in range(N)]
X = [0 for _ in range(N)]
P = [0 for _ in range(N)]

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

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


def dfs(p, x, parent):

    P[p] += x + X[p]
    for node in G[p]:
        if node == parent:
            continue
        dfs(node, x + X[p], p)


dfs(0, 0, -1)

print(' '.join([str(p) for p in P]))


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

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

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
### BUGGY CODE ###

from heapq import heappush, heappop

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

jobs = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

ans = 0
heap = []
for day in range(1,M+1):
	for i in jobs:		
		if i[0] == day:
			heappush(heap, -i[1])
		elif i[0] > day:
			break
    
	if len(heap) > 0:
		ans += -heappop(heap)

print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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

import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def main():
    N,D,A = LI()
    M = []
    for i in range(N):
        M.append(LI())
    M.sort(key = lambda x: x[0])
    
    count = 0
    for i in range(N):
        if M[i][1] > 0:
            bomb = (M[i][1]+A-1)//A
            count += bomb
            damage = bomb * A
            for j in range(i,N):
                if M[j][0] <= M[i][0] + 2*D:
                    M[j][1] -= damage
                else:
                    break

    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = zip(*sorted(zip(m,m)))
    
    over = [-1]*N
    tmp=0
    for i in range(N):
      while(tmp<N and X[i]+D*2>=X[tmp]):
        tmp += 1
      over[i] = tmp
    reset = [0]*N
    
    ans = 0
    dam = 0
    for i in range(N):
      if i>0:
        reset[i] += reset[i-1]
      hp = H[i]-dam+reset[i]
      if hp > 0:
        bomb = (hp+A-1)//A
        ans += bomb
        dam += bomb * A
        if(over[i]<N):
          reset[over[i]] += bomb * A

    print(ans)

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

H, W, D = list(map(int, input().split()))

A = []
for i in range(H):
  A.append(list(map(int, input().split())))
  
Q = int(input())

LR = []

for i in range(Q):
  LR.append(list(map(int, input().split())))

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(i, H * W - D, D):
    a = List[j]
    b = List[j + D]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1])
    
Ans = [[0 for i in range(H * W)] for j in range(H * W)]
for i in range(H * W - D):
  t = Data[i]
  for j in range(i + D, H * W, D):
    Ans[i][j] = t
    t += Data[j]
    
for i in range(Q):
  print(Ans[LR[i][0] - 1][LR[i][1] - 1])
    

### FIXED CODE ###

H, W, D = list(map(int, input().split()))

A = []
for i in range(H):
  A.append(list(map(int, input().split())))
  
Q = int(input())

LR = []

for i in range(Q):
  LR.append(list(map(int, input().split())))

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(D + i, H * W, D):
    a = List[j - D]
    b = List[j]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1]) + Data[j - D]

for i in range(Q):
  print(Data[LR[i][1] - 1] - Data[LR[i][0] - 1])
### BUGGY CODE ###

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

cnt = 0
for i in range(N):
    Flg = True
    for j in range(i):
        if P[j] < P[i]:
            Flg = False
            break
    if Flg:
        cnt += 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
min_value = N + 1
for i in range(N):
    if P[i] <= min_value:
        cnt += 1
        min_value = P[i]
print(cnt)
### BUGGY CODE ###

def check(c):
    l = [['.']*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            l[(i+c)%n][j] = s[i][j]
    for i in range(n):
        for j in range(n):
            if l[i][j]!=l[j][i]:
                return False
    return True
n = int(input())
s = [input() for _ in range(n)]
ans = 0
for c in range(n):
    if check(c):
        ans+=n
print(ans)

### FIXED CODE ###

def check(c):
    l = [['.']*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            l[(i+c)%n][j] = s[i][j]
    for i in range(n):
        for j in range(n):
            if l[i][j]!=l[j][i]:
                return False
    return True
n = int(input())
s = [input() for _ in range(n)]
ans = 0
for c in range(n):
    if check(c):
        ans+=n
print(ans)
### BUGGY CODE ###

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])

### FIXED CODE ###

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = [0]
value = [0]
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    i += 1
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i][sum_w] = max(dp[i][sum_w], dp[i-1][sum_w])

print(dp[N][W])
### BUGGY CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)
dp[0] = 0
for i in range(1,H+1):
    for j in range(N):
        dp[i] = min(dp[i], dp[max(i-A[j],0)] + B[j])
            
print(int(dp[H]))

### FIXED CODE ###

import numpy as np

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

A = np.zeros(N, dtype = int)
B = np.zeros(N, dtype = int)

for i in range(N):
    A[i],B[i] = map(int,input().split())
    
dp = np.full(H+1, np.inf)

dp[0] = 0
for i in range(1,H+1):
    dp[i] = np.amin( dp[np.maximum(i-A,0)] + B )

print(int(dp[H]))
### BUGGY CODE ###

a=int(input())
b = 1
for i in range(1,a+1):
    b *= i
print(b%1000000007)

### FIXED CODE ###

from math import factorial
print(factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * num_city for i in range(0, num_city)]
for i in range(0, num_train):
    start, arrive = [int(j) - 1 for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * num_city for i in range(0, num_city)]
for start in range(0, num_city):
    for arrive in range(0, num_city):
        if arrive != 0:
            trains_cumulative_sum[start][arrive] += trains_cumulative_sum[start][arrive - 1]
        trains_cumulative_sum[start][arrive] += trains[start][arrive]

answers = []
for i in range(0, num_question):
    start, arrive = [int(j) - 1 for j in input().split()]
    result = 0
    for j in range(start, arrive + 1):
        result += trains_cumulative_sum[j][arrive]
    answers.append(result)

for answer in answers:
    print(answer)


### FIXED CODE ###

num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
cumlative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] = cumlative_sum[start][arrive - 1] + trains[start][arrive]

for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] += cumlative_sum[start - 1][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = cumlative_sum[arrive][arrive] - cumlative_sum[start - 1][arrive] - cumlative_sum[arrive][start - 1] + cumlative_sum[start - 1][start - 1]
    print(result)