Harryxun/stf_run huggingface dataset:
l,r = map(int, input().split())


a=l%2019
b=r%2019
ans=99999999
for i in range(a,b+1):
  for j in range(i+1,b+1):
  tmpans=(i*j)%2019
  if ans>tmpans:
    ans=tmpans
print(ans)
    


### FIXED CODE ###

def baisuaru(l,r,m):
  if l//m < r//m:
    return True
  elif l%m==0:
    return True
  else:
    return False
    

l,r = map(int, input().split())


if baisuaru(l,r,2019):
  print(0)
else:
  if baisuaru(l,r,3) and baisuaru(l,r,673):
    print(0)
  else:
    a=l%2019
    b=r%2019
    ans=99999999
    for i in range(a,b+1):
      for j in range(i+1,b+1):
        tmpans=(i*j)%2019
        if ans>tmpans:
          ans=tmpans
    print(ans)
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
    
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)
n,q=list(map(int,input().split()))

ab=[[] for _ in range(n)]
arr=[0 for _ in range(n)]
cache=[[] for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  ab[a-1].append(b-1)

px=[list(map(int,input().split())) for _ in range(q)]
  
  
def search(tree, root):
  arr=[]
  children=tree[root]
  if children == []:
    return None
  else:
    arr.extend(children)
    for child in children:
      ret=search(tree, child)
      if ret is not None:
        arr.extend(ret)    
  return arr


for p,x in px:
  if cache[p-1] == []:
    children=search(ab,p-1)
    if children is not None:
      children=[p-1]+children
    else:
      children=[p-1]
    cache[p-1]=children
    for child in children:
      arr[child]+=x
  else:
    for child in cache[p-1]:
      arr[child]+=x    
print(*arr)
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


def dfs(v, p):
    for next_v in g[v]:
        if next_v == p:
            continue
        cnt[next_v] += cnt[v]
        dfs(next_v, v)


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

g = {i:[] for i in range(N+1)}
cnt = {i:0 for i in range(N+1)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x

dfs(1, -1)

print(*list(cnt.values())[1:])
n=int(input())
temp=[0]*n
for i in range(0,n):
  s,p=input().split()
  temp[i]=[i,s,int(p)]
temp=sorted(temp, key=lambda x: (x[1],-x[2]))
for i in range(0,n)
  print(temp[i])



### FIXED CODE ###

n=int(input())
temp=[0]*n
for i in range(0,n):
  s,p=input().split()
  temp[i]=[i,s,int(p)]
temp=sorted(temp, key=lambda x: (x[1],-x[2]))
for i in range(0,n):
  print(temp[i][0]+1)
N,K = int(input().split())
h = [int(input()) for i in range(N)]
 
 
list2=list()
 
h.sort()
 
for i in range(N-K):
    list2.append(h[i+K]-h[i+1])
    continue
print(min(list2))

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]

list2=list()
h.sort()

for i in range(N-K+1):
    list2.append(h[i+K-1]-h[i])
    continue
print(min(list2))
a, b, c = map(int, raw_input().split())
 
if a < b and b < c:
 print "yes"
else
 print "no"

### FIXED CODE ###

a, b, c = map(int, raw_input().split())
  
if a < b and b < c:
 print "Yes"
else:
 print "No"
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush


h,w,m=[int(x) for x in input().split()]

#defaultdictにすることにより後に使うmax関数のコストを削減
hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=set()
#O(H)
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add([hi,wi])

#O(H)
hmax=max(hcnt.values())
wmax=max(wcnt.values())

#O(H)
hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

#O(H**2)
ofst=-1
for i in hidx:
    for j in widx:
        if not [i,j] in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict
from heapq import heapify
from heapq import heappop
from heapq import heappush
from _collections import defaultdict

h,w,m=[int(x) for x in input().split()]

hcnt=defaultdict(int)
wcnt=defaultdict(int)
bomb=set()
for _ in range(m):
    hi,wi=[int(x)-1 for x in input().split()]
    hcnt[hi]+=1
    wcnt[wi]+=1
    bomb.add((hi,wi))

hmax=max(hcnt.values())
wmax=max(wcnt.values())

hidx=[x for x,y in hcnt.items() if y==hmax]
widx=[x for x,y in wcnt.items() if y==wmax]

ofst=-1
for i in hidx:
    for j in widx:
        if not (i,j) in bomb:
            ofst=0
            break
                
print(hmax+wmax+ofst)
n,k=map(int,input().split())
h=list(map,int(input().split()))

ans=0

for hh in h:
  if hh>=k:
    ans+=1
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))

ans=0

for hh in h:
  if hh>=k:
    ans+=1
print(ans)
N = input()
N_1 = N[-3] + N[-2] + N[-1]

if N_1 == "000":
    print(0)
else:
    print(1000-int(N_1))

### FIXED CODE ###

N = input()

if len(N) <= 2:
    print(1000 - int(N)) 
    
else:
    N_1 = N[-3] + N[-2] + N[-1]
    if N_1 == "000":
        print(0)
    else:
        print(1000-int(N_1))
N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N+1)]

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    now_card = X[i]
    for j in range(N+1):
        for s in range(50*N+1):
            if s >= now_card:  # 今見ているのはX[i], これをどうするかで遷移先を変更する
                dp[i+1][j+1][s] += dp[i][j][s-now_card]  # 追加する余裕がある場合は追加する
            dp[i+1][j][s] += dp[i][j][s]  # 何も追加しない
ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
print(ans)


### FIXED CODE ###

N, A = map(int, input().split())  # N枚のカード, 平均をAにしたい

X = tuple(map(int, input().split()))  # カードリスト

# [カードの総枚数][選んだカードの枚数][今の総和]
dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N+1)]

# 0枚の中から0枚選んで総和が0になるパターンは1つ
dp[0][0][0] = 1

for i in range(N):
    for j in range(N+1):
        for k in range(N*50+1):
            if dp[i][j][k]:  # 今の状態を未来へ遷移させる処理
                dp[i+1][j][k] += dp[i][j][k]  # 何も加えず未来へ
                dp[i+1][j+1][k+X[i]] += dp[i][j][k]  # 今見ているカードを加えて未来に遷移

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

print(ans)
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = []
c = []
i = 0
while i < n*(n-1)//2:
    m = n - i
    for j in range(i+1):
        c = a[j:j + m]
        if sum(c) != 0:
            b.append(sum(c))
    i += 1
d = sorted(b, reverse=True)
for i in range(k):
    c.append(d[i])

ans = d[0]
for i in range(k):
    if i+1 == len(c):
        break
    ans = ans & c[i+1]
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ave = sum(a) / n
b = 10000000
c = 0
for i in range(n):
    if b > abs(ave - a[i]):
        b = abs(ave - a[i])
        c = i
print(c)
def solve():
    N, M = map(int, input().split())
    d = {}

    if N == 1:
        s, c = map(int, input().split())
        return c

    for i in range(M):
        s, c = map(int, input().split())
        if (s in d and d[s] != c) or (s == 1 and c == 0):
            return -1
        else:
            d[s] = c
    
    ans = [0] * N
    for key, val in d.items():
        ans[key - 1] = val
    if ans[0] == 0:
        ans[0] = 1
    ans = [str(c) for c in ans]

    return "".join(ans)

print(solve())

### FIXED CODE ###

N, M = map(int, input().split())
sc = []
for i in range(M):
    sp, cp = map(int, input().split())
    sc.append((sp, cp))

ans = 10000

if N == 1:
    for i in range(10):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])):
                flag = False
                break
        if flag:
            ans = min(ans, i)
else:
    for i in range(10 ** (N - 1), 10 ** N):
        num = str(i)
        flag = True
        for pair in sc:
            if (num[pair[0] - 1] != str(pair[1])) or len(num) < pair[0]:
                flag = False
                break
        if flag:
            ans = min(ans, i)

if ans == 10000:
    ans = -1
print(ans)
N, K = map(int, input().split())
S = input()

before = S[0]
cnt = 0
same_nums = []
for i in range(N):
  if S[i] == before:
    cnt += 1
  else:
    same_nums.append(cnt)
    before = S[i]
    cnt = 1
same_nums.append(cnt)
if S[0] == '0':
  sum_temp = sum(same_nums[:2*K+1])
  ans = sum_temp
  for i in range(0, K+1, 2):
    sum_temp = sum_temp - sum(same_nums[i:i+2]) + sum(same_nums[i+2*K+1:i+2*K+3])
    ans = max(ans, sum_temp)
  print(ans)
else:
  sum_temp = sum(same_nums[:2*K])
  ans = sum_temp
  sum_temp = sum_temp - same_nums[1] + sum(same_nums[2*K:2*K+2])
  ans = max(ans, sum_temp)
  for i in range(3, K+1, 2):
    sum_temp = sum_temp - sum(same_nums[i:i+2]) + sum(same_nums[i+2*K:i+2*K+2])
    ans = max(ans, sum_temp)
  print(ans)
  


### FIXED CODE ###

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

before = S[0]
cnt = 0
same_nums = []
if S[0] == '0':
  same_nums.append(0)
for i in range(N):
  if S[i] == before:
    cnt += 1
  else:
    same_nums.append(cnt)
    before = S[i]
    cnt = 1
same_nums.append(cnt)
if S[-1] == '0':
  same_nums.append(0)
  
sum_nums = sum(same_nums[:2*K+1])
ans = sum_nums
for i in range(0, len(same_nums)-2*K, 2):
  sum_nums = sum_nums - sum(same_nums[i:i+2]) + sum(same_nums[i+2*K+1:i+2*K+3])
  ans = max(ans, sum_nums)
print(ans)
a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=0
    t=0
    for i in range(41):
        if 2**i>a:
            s=i
            break
    for i in range(41):
        if 2**i>b:
            t=i-1
            break
    ans=0
    for j in range(a,2**s):
        ans=ans^j
    for j in range(2**t,b+1):
        ans=ans^j
	print(ans)


### FIXED CODE ###

a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=4-a%4
    t=(1+b%4)
    ans=0
    for j in range(a,a+s):
        ans=ans^j
    for j in range(b+1-t,b+1):
        ans=ans^j
    print(ans)
def m(n,r):
    d=1
    c=1
    for i in range(r):
        d*=(n-i)
        c*=(i+1)
    return(int(d/c))

n=[int(i) for i in input().split()]
a=sum(n)
c=max(n)-min(n)
if a%3 != 0:print(0)
elif c!=0 and a/c < 0.5:print(0)
else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        if c==0:
            c=int(b/2)
        d=m(b,c)
        print(d%(10**9+7))

### FIXED CODE ###

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)

def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    #print(inv, q, gcd_val)
    return inv % m

def m(n,r):
    d=1
    e=1
    f=1
    for i in range(r):
        d=(n-i)
        e=(i+1)
        d%=(10**9+7)
        f = f*d*modinv(e,(10**9+7))%(10**9+7)
        
    return(f)

n=[int(i) for i in input().split()]
a=sum(n)
if a%3 != 0:print(0)

else:
    b=int(a/3)
    if b==1:
        print(1)
    else:
        c=n[0]-b
        d=n[1]-b
        if c<0 or d<0: print(0)

        else:
            if c==d:
                c=int(b/2)
            d=m(b,min(c,d))
            print(d%(10**9+7))
def resolve():
    h, w  = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    ans = []
    for i in range(h):
        for j in range(w):
            if j != w-1 :
                if a[i][j] % 2 == 0:
                    continue
                else:
                    ans.append([i, j, i, j+1])
                    a[i][j+1] += 1
    for i in range(h):
        if i != h-1:
            if a[i][w-1] & 2 == 0:
                continue
            else:
                ans.append([i, j, i+1, j])
                a[i][j+1] += 1
    print(len(ans))
    for i in range(len(ans)):
        print(*ans[i])
resolve()

### FIXED CODE ###


def resolve():
    h, w  = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    ans = []
    for i in range(h):
        for j in range(w):
            if j != w-1 :
                if a[i][j] % 2 == 0:
                    continue
                else:
                    ans.append([i+1, j+1, i+1, j+2])
                    a[i][j+1] += 1
                    a[i][j] -= 1
    for i in range(h):
        if i != h-1:
            if a[i][w-1] % 2 == 0:
                continue
            else:
                ans.append([i+1, j+1, i+2, j+1])
                a[i+1][w-1] += 1
                a[i][w-1] -= 1
    print(len(ans))
    for i in range(len(ans)):
        print(*ans[i])
resolve()
while 1:
   a, op, b = map(raw_input().split())
   A = int(a)
   B = int(b)

   if op == "?":
      break
   elif op == "+":
      print A+B
   elif op == "-":
      print A-B
   elif op == "*":
      print A*B
   elif op == "/":
      print A/B

### FIXED CODE ###

while 1:
   a, op, b = raw_input().split()
   A = int(a)
   B = int(b)
 
   if op == '?':
      break
   elif op == '+':
      print A+B
   elif op == '-':
      print A-B
   elif op == '*':
      print A*B
   elif op == '/':
      print A/B
n = int(input())
a=[]
for i in range(n):
  a.append(int(input()))
c = 1
k = a[1]
while k != 1:
  if k == 2:
    print(c)
  k = a[k]
  c += 1
print(-1)  
  


### FIXED CODE ###

n = int(input())
a=[0]
for i in range(n):
  a.append(int(input()))
c = 1
k = a[1]
while c <= n:
  if k == 2:
    print(c)
    exit()
  k = a[k]
  c += 1
print(-1)
import itertools
import math
MOD = 1000000007
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)% MOD
def X(n, r):
  try:
    return C(n-1,n-r) 
  except:
    return 0
N,K = map(int,input().split())

for i in range(1,K+1):
  if (1==i and K==N):
    print (1)
  else:
    #ßprint (X(K,i)*((X(N-K,i+1)+2*X(N-K,i)+X(N-K,i-1)))% MOD)
    print (C(N-K+1,i)*C(K-1,i-1)% MOD)


### FIXED CODE ###

import itertools
import math
MOD = 1000000007
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)% MOD
def X(n, r):
  try:
    return C(n-1,n-r) 
  except:
    return 0
N,K = map(int,input().split())

for i in range(1,K+1):
  if (1==i and K==N):
    print (1)
  else:
    print (X(K,i)*((X(N-K,i+1)+2*X(N-K,i)+X(N-K,i-1)))% MOD)
from itertools import product as prod

n = int(input().strip())
s = [int(input()) for _ in range(n)]
ans = 0
for elem in (prod([0, 1], repeat=10)):
    rep = 0
    for i in range(n):
        if elem[i]:
            rep += s[i]
    if rep % 10 == 0:
        rep = 0
    ans = max(ans, rep)
print(ans)


### FIXED CODE ###

n = int(input().strip())
s = [int(input()) for _ in range(n)]
s.sort()
su = sum(s)
if su % 10 == 0:
    for elem in s:
        if (su - elem) % 10 != 0:
            print(su - elem)
            exit()
    print(0)
else:
    print(su)
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[]
dp.append(0)
dp.append(abs(h[1]-h[0]))
for i in range(2,n):
  dp.append(min(dp[j]+abs(h[i]-h[j]) for j in range(i-k,i)))
print(dp[n-1])

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	h = list(map(int, input().split()))
	dp=[0]*N
	for i in range(1,N):
		dp[i] = min(dp[g] + abs(h[i] - h[g]) for g in range(max(i-K,0), i))
	print(dp[N-1])
main()
N = int(input())
S = input()

prev = None
for i in S:
  if prev != i:
  	prev = i
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()

prev = None
count = 0

for i in S:
  if prev != i:
    prev = i
    count += 1
    
print(count)
b = int(input())
c = int(input())
x = int(input())
i1, i2, i3 = 0, 0, 0
m, p = 0, 0
while i1 <= a:
  while i2 <= b:
    while i3 <= c:
      m = 500 * i1 + 100 * i2 + 50 * i3
      if m == x:
        p += 1
      i3 += 1
    i3 = 0
    i2 += 1
  i2 = 0
  i1 += 1
print(p)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())
i1, i2, i3 = 0, 0, 0
m1, m2, m3, p = 0, 0, 0, 0
while i1 <= a:
  m1 = 500 * i1
  while i2 <= b:
    m2 = m1 + 100 * i2
    while i3 <= c:
      m3 = m2 + 50 * i3
      if m3 < x:
        i3 += 1
        continue
      elif m3 > x:
        break
      else:
        p += 1
        break
    i3 = 0
    i2 += 1
  i2 = 0
  i1 += 1
print(p)
import math
input_a= input().split(" ")
X=int(input_a[0])
N=int(input_a[1])

if N!=0:
  array= input().split(" ")
else:
  array=[0,0]

num=X
num2=-100
for i in range(101-X):

  
  if str(num) not in array:
    dis=abs(X-num)
    num2=X-dis
    num1=num
    if str(num2) not in array:
    	numa=min([num,num2])
    else:
      numa=num1
    break
  num=num+1
    

num=X
i=0
for i in range(X+3):
  
  if str(num) not in array:
    
    dis2=abs(X-num)
    num3=X+dis2
    #print(num,dis2,num3)
    if str(num3) not in array:
    	numb=min([num,num3])
    else:
      numb=num
      break
  num=num-1
#print(numa,numb,dis,dis2)
if dis<dis2:
  print(numa)
elif dis==dis2:
  print(numb)
else:
  print(numb)

### FIXED CODE ###

import math
input_a= input().split(" ")
X=int(input_a[0])
N=int(input_a[1])
dis=X+3
dis2=100
if N!=0:
  array= input().split(" ")
else:
  array=[0,0]

num=X
num2=-100
for i in range(N+1):

  
  if str(num) not in array:
    dis=abs(X-num)
    num2=X-dis
    num1=num
    if str(num2) not in array:
    	numa=min([num,num2])
    else:
      numa=num1
    break
  num=num+1
    

num=X
i=0
for i in range(dis):
  
  if str(num) not in array:
    
    dis2=abs(X-num)
    num3=X+dis2

    if str(num3) not in array:
    	numb=min([num,num3])
    else:
      numb=num
      break
  num=num-1

if dis<dis2:
  print(numa)
elif dis==dis2:
  print(numb)
else:
  print(numb)
W, H, x, y, r = map(int, input(), split())
if ((x-r) >= 0) and ((x+r) <= W) :
    if((y-r) >= 0) and ((y+r) <= H) :
        print ("Yes")
    else :
        print ("No")
else :
    print ("No")

### FIXED CODE ###

W, H, x, y, r = map(int, input().split())
if ((x-r) >= 0) and ((x+r) <= W) :
    if((y-r) >= 0) and ((y+r) <= H) :
        print ("Yes")
    else :
        print ("No")
else :
    print ("No")
a,b,c,d = map(int,input().split())
import math

def num_of_complements(x,c,d):
    lcm = c * d // math.gcd(c, d)
    num = x + x//lcm - x//c - x//d
    return num

ans = num_of_complements(b,c,d) - num_of_complements(a-1,c,d)
print(ans)


### FIXED CODE ###

a,b,c,d = map(int,input().split())
from fractions import gcd
lcm = c * d // gcd(c, d)
def num_of_complements(x,c,d,lcm):
    num = x + x//lcm - x//c - x//d
    return num

ans = num_of_complements(b,c,d,lcm) - num_of_complements(a-1,c,d,lcm)
print(ans)
if int(inout())%9==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

if int(input())%9==0:
  print("Yes")
else:
  print("No")
k, s = map(int, input().split())

ans = 0

for x in range(k+1):
  if x > s:
    break
  for y in range(k+1):
    if sum(x, y) > s:
      break
    for z in range(k+1):
      if sum(x, y, z) > s:
        break
      if sum(x, y, z) == s:
        ans += 1

print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
    z = s - x - y
    if 0 <= z <= k:
      ans += 1

print(ans)
N = int(input())
P = list(map(lambda a: int(a) - 1, input().split()))

ans = 0
for i in range(N):
    p = P[i]
    if p == i and i < N:
        P[i], P[i + 1] = P[i + 1], P[i]
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
P = list(map(lambda a: int(a) - 1, input().split()))

ans = 0
for i in range(N):
    p = P[i]
    if p == i:
        if i < N - 1:
            P[i], P[i + 1] = P[i + 1], P[i]
        ans += 1

print(ans)
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define IREP(i, n) for(int i = (int)(n) - 1; i >= 0; i--)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LLONG_MAX
#define LMIN LLONG_MIN
template<typename T> inline void chmin(T &a, T b){ if(a > b) a = b; }
template<typename T> inline void chmax(T &a, T b){ if(a < b) a = b; }
template<typename T> inline void xch(T &a, T &b){ T w = a; a = b; b = w; }


int main() {
    int H, N;
    cin >> H >> N;
    int A[N], B[N];
    REP(i, N){
        cin >> A[i] >> B[i];
    }
    ll dp[10001];
    REP(i, 10001) dp[i] = (ll)1e10;
    dp[0] = 0;
    REP(i, N){
        REP(j, 10001){
            int next = min(j + A[i], H);
            dp[next] = min(dp[next], dp[j] + B[i]);
        }
    }
    cout << dp[H] << endl;
    return 0;
}


### FIXED CODE ###

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [10000000000] * 10001
dp[0] = 0
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp[next] = min(dp[next], dp[j] + B[i])
print(dp[H])
from operator import mul
from functools import reduce

MOD = 10**9 + 7


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


N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
A_rev = list(reversed(A))


ans = 0
C = cmb(N-1, K-1)
for i, j in zip(A, A_rev):
    if N < K:
        break
    ans += C * j
    ans -= C * i
    ans %= MOD
    try:
        C = C * (N - K) / (N - 1)
    except ZeroDivisionError:
        break
    N -= 1
print(int(ans % MOD))


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
A.sort()
MOD = 10 ** 9 + 7


def combination(mod=MOD):
    fact = [1] * (N + 1)
    inv_fact = [1] * (N + 1)
    r = 1
    for i in range(1, N + 1):
        fact[i] = r = r * i % mod
    inv_fact[N] = r = pow(fact[N], mod - 2, mod)
    for i in range(N, 0, -1):
        inv_fact[i - 1] = r = r * i % mod

    def _wrapper(n, k):
        nonlocal fact, inv_fact, mod
        if n == 0 or k == 0:
            return 1
        return fact[n] * inv_fact[k] * inv_fact[n - k] % mod

    return _wrapper


def main():
    if K == 1:
        print(0)
        exit()
    comb = combination()
    sum_max = 0
    sum_min = 0
    for i, A_i in enumerate(A):
        if i >= K - 1:
            sum_max += comb(i, K - 1) * A_i % MOD
        if N - i >= K:
            sum_min += comb(N - i - 1, K - 1) * A_i % MOD
    ans = (sum_max - sum_min) % MOD
    print(ans)


if __name__ == '__main__':
    main()
import numpy as np

# S = list(input())
n, l = list(map(int, input().split()))

RINGO = list(np.array(list(range(1, n+1))) + l - 1)
AJI = list(map(abs, RINGO))

RINGO.remove(min(AJI))
print(sum(RINGO))


### FIXED CODE ###

import numpy as np

# S = list(input())
n, l = list(map(int, input().split()))

RINGO = list(np.array(list(range(1, n+1))) + l - 1)
AJI = list(map(abs, RINGO))

RINGO.pop(AJI.index(min(AJI)))
print(sum(RINGO))