Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<np and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    if r==l:
      break
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,k=map(int,input().split())
a=list(map(int,input().split()))
ap,an=[],[]
zeronum=0
for i in range(n):
  if a[i]>0:
    ap.append(a[i])
  elif a[i]<0:
    an.append(-a[i])
  else:
    zeronum+=1
np,nn=len(ap),len(an)
def fminus(x):
  j=0
  cnt=0
  for i in range(np):
    cnt+=j
    while j<nn and an[j]*ap[i]>=x:
      j+=1
      cnt+=1
  return cnt
def fplus(x,length,lis):
  r=length-1
  cnt=0
  for l in range(length):
    while lis[r]*lis[l]>x:
      if r==l:
        break
      r-=1
    if r==l:
      break
    elif lis[r]*lis[l]<=x:
      cnt+=r-l
  return cnt
if np*nn<k<=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn):
  print(0)
else:
  #print(ap)
  #print(an)
  if k<=np*nn:
    an.sort(reverse=True)
    ap.sort()
    ng=10**18
    ok=0
    while ng-ok>1:
      mid=(ok+ng)//2
      if fminus(mid)>=k:
        ok=mid
      else:
        ng=mid
    print(-ok)
  else:
    an.sort()
    ap.sort()
    k-=np*nn+zeronum*(zeronum-1)//2+zeronum*(np+nn)
    #print(k)
    ok=10**18
    ng=0
    #print(ok,ng)
    while ok-ng>1:
      mid=(ok+ng)//2
      if fplus(mid,nn,an)+fplus(mid,np,ap)>=k:
        ok=mid
      else:
        ng=mid
    print(ok)
n,m = map(int,input().split())
h = list(map(int,input().split())
judge = [True] * n

for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] >= h[b-1]:
        judge[b-1] = False
    else:
        judge[a-1] = False
        
print(judge.count(True))

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
judge = [True] * n

for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] == h[b-1]:
        judge[a-1],judge[b-1] =False, False
    elif h[a-1] > h[b-1]:
        judge[b-1] = False
    else:
        judge[a-1] = False

print(judge.count(True))
a=input()
s=list(map(int, input().split()))
bad=0
for i in s:
    if s%2==0:
        if s%3!=0 or s%5!=0:
            bad+=1
if bad>0:
    print('DENIED') 
else:
    print('APPROVED')



### FIXED CODE ###

a=int(input())
s=list(map(int,input().split()))
count=0
good=0
for i in s:
    if i%2==0:
        count+=1
        if i%3==0 or i%5==0:
            good+=1
if good==count:
    print('APPROVED')
else:
    print('DENIED')
#!/usr/bin/env python
# coding: utf-8

# In[13]:


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


# In[15]:


if N != 100:
    print(N*(100**D))
elif n == 100:
    print((N+1)*100**D)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[13]:


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


# In[15]:


if N != 100:
    print(N*(100**D))
elif N == 100:
    print((N+1)*100**D)


# In[ ]:
N = int(input())
n = "Three"

for i in range(N):
  S = input().split()
  If S == "Y":
    n = "Four"
    break

print(n)
    

  

### FIXED CODE ###

N = int(input())
number = "Three"
S = input().split()

for i in range(N):
  if S[i] == "Y":
    number = "Four"
    break

print(number)
sum = 0
while 1:
   x = raw.input()
   sum = sum + 1
   if x == "0":
      break
for i in range(0,sum):
   print 'Case %s: %s' %(i, x)

### FIXED CODE ###

sum = 0
while 1:
   x = raw_input()
   sum = sum + 1
   if x == '0':
      break
   print 'Case %s: %s' %(sum, x)
d,n  = map(int,input().split())
l1 = []
l2 = []


        
if d == 0:
    print(n)
elif d == 1:
    if n != 100:
        print(n * 100)
    else:
        print(10100)
else:
    if n! = 100:
        print(n * 10000)
    else:
        print(1010000)

### FIXED CODE ###

d,n  = map(int,input().split())
l1 = []
l2 = []


        
if d == 0:
    if n != 100:
        print(n)
    else:
        print(101)
elif d == 1:
    if n != 100:
        print(n * 100)
    else:
        print(10100)
else:
    if n != 100:
        print(n * 10000)
    else:
        print(1010000)
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

x = INT()

if x % 11 == 0:
    print(2 * x // 11)
else:
    if 6 < x % 11:
        tmp = 2 + 2 * (x // 11)
    else:
        tmp = 1 + 2 * (x // 11)
print(tmp)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

x = INT()

if x % 11 == 0:
    tmp = 2 * x // 11

else:
    if 6 < x % 11:
        tmp = 2 + 2 * (x // 11)
    else:
        tmp = 1 + 2 * (x // 11)
print(tmp)
a, b, c = map(int,input().split())
ans = False
if a == b + c or b = a + c or c = a + b:
    ans = True
if ans:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a, b, c = map(int,input().split())
ans = False
if a == b + c or b == a + c or c == a + b:
    ans = True
if ans:
    print("Yes")
else:
    print("No")
import math

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

if b!=1:
  num = math.ceil(((b-1)/(a-1))
else:
  num = b

print(num)

### FIXED CODE ###

import math

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

if b!=1:
  num = math.ceil((b-1)/(a-1))
else:
  num = 0

print(num)
a = input()
print(a+a*a+a*a*a)


### FIXED CODE ###

a = int(input())
print(a+a*a+a*a*a)
a,b,c,x,y=map(int,input().split())

m=max(x,y)
ans=10**9+7
for e in range(m+1):
  ans=min(ans,2*e*c+a*max(0,x-e)+b*(0,y-e))
  
print(ans)

### FIXED CODE ###

a,b,c,x,y=map(int,input().split())

m=max(x,y)
ans=10**9+7
for e in range(m+1):
  ans=min(ans,2*e*c+a*max(0,x-e)+b*max(0,y-e))
  
print(ans)
import math

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


def main():
	a,b = map(int, input().split())
	num = math.gcd(a,b)
	if num == 1:
		print(1)
		exit()
	result_list = factorize(num)
	print(len(set(result_list)) + 1)			
	


if __name__ == "__main__":
	main()


### FIXED CODE ###

import os

def main():
	n = int(input())
	if n%2 == 0:
		print((n//2)/n)
	else:
		print(((n//2)+1)/n)


if __name__ == "__main__":
	main()
n,a,b = map(int,input(),split())
print(min(a*n,b))

### FIXED CODE ###

n,a,b = map(int,input().split())
print(min(a*n,b))
import sys

X = int(input())

if X == 1:
	print(1)
elif X > 1:
	for i in range(2,1000000000):
		if X <= i*(i + 1)/2:
			t = i
			break
print(i)

### FIXED CODE ###

import sys

X = int(input())

if X == 1:
	print(1)
elif X > 1:
	for i in range(2,1000000000):
		if X <= i*(i + 1)/2:
			t = i
			print(i)
			break
n, k = map(int,input().split())
d = int(input())
for x in range(k + 1):
    input()
print(n-d)

### FIXED CODE ###

n, k = map(int,input().split())
sn = [0 for x in range(n)]
for kind in range(k):
    d = int(input())
    a_lis = list(map(int,input().split()))
    for a in a_lis:
        sn[a-1] += 1
print(sn.count(0))
N=int(input())
t=[0]*N
r=set(range(N))
for _ in[0]*N:
 x,y,z=map(int,input().split())
 t[x]=[y,z]+[0]*5
 r-={y,z}
def f(i,p,s,d):
 if i<0:return-1
 l,r=t[i][:2]
 t[i][2:5]=[p,s,(l!=-1)+(r!=-1),d]
 return t[i][6]=max(f(l,i,r,d+1),f(r,i,l,d+1))+1
f(r.pop(),-1,-1,0)
for i in range(N):
 print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i,*t[i][2:],'root'if not t[i][5]else'internal node'if t[i][4]else'leaf'))


### FIXED CODE ###

N=int(input())
t=[0]*N
r=set(range(N))
for _ in[0]*N:
 x,y,z=map(int,input().split())
 t[x]=[y,z]+[0]*5
 r-={y,z}
def f(i,p,s,d):
 if i<0:return-1
 k=t[i]
 l,r=k[:2]
 k[2:]=[p,s,(l!=-1)+(r!=-1),d,max(f(l,i,r,d+1),f(r,i,l,d+1))+1]
 return t[i][-1]
f(r.pop(),-1,-1,0)
for i in range(N):
 print('node {}: parent = {}, sibling = {}, degree = {}, depth = {}, height = {}, {}'.format(i,*t[i][2:],'root'if not t[i][5]else'internal node'if t[i][4]else'leaf'))
from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-float("inf"))
t.append(-float("inf"))
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(float("inf"))
t.append(float("inf"))
s.sort()
t.sort()
for i in range(q):
    x=int(input())
    ans=float("inf")
    tmp_s_1=bisect.bisect_left(s,x)-1
    tmp_s_2=tmp_s_1+1
    tmp_s_1_t=bisect.bisect_left(t,s[tmp_s_1])
    tmp_s_2_t=bisect.bisect_left(t,s[tmp_s_2])
    ans=min(abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t-1]), abs(x-s[tmp_s_1])+abs(s[tmp_s_1]-t[tmp_s_1_t]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t-1]), abs(x-s[tmp_s_2])+abs(s[tmp_s_2]-t[tmp_s_2_t]))
    tmp_t_1=bisect.bisect_left(t,x)-1
    tmp_t_2=tmp_t_1+1
    tmp_t_1_s=bisect.bisect_left(s,t[tmp_t_1])
    tmp_t_2_s=bisect.bisect_left(s,t[tmp_t_2])
    ans=min(ans, abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s-1]), abs(x-t[tmp_t_1])+abs(t[tmp_t_1]-s[tmp_t_1_s]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s-1]), abs(x-t[tmp_t_2])+abs(t[tmp_t_2]-s[tmp_t_2_s]))
    print(ans)

### FIXED CODE ###

from bisect import bisect_left
a,b,q=map(int,input().split())
s=[]
t=[]
x=[]
s.append(-10**12)
t.append(-10**12)
for i in range(a):
    s.append(int(input()))
for i in range(b):
    t.append(int(input()))
s.append(10**12)
t.append(10**12)
for i in range(q):
    x=int(input())
    tmp_s=bisect_left(s,x)-1
    tmp_s_1=s[tmp_s]
    tmp_s_2=s[tmp_s+1]
    tmp_t=bisect_left(t,x)-1
    tmp_t_1=t[tmp_t]
    tmp_t_2=t[tmp_t+1]
    print(min(abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_1),
    abs(x-tmp_s_1)+abs(tmp_s_1-tmp_t_2),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_1),
    abs(x-tmp_s_2)+abs(tmp_s_2-tmp_t_2),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_1),
    abs(x-tmp_t_1)+abs(tmp_t_1-tmp_s_2),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_1),
    abs(x-tmp_t_2)+abs(tmp_t_2-tmp_s_2)))
N = int(input())
aN = [ int(i) for i in input().split() ]
aN.reverse()
bN = []

for a in aN:
    if len([b for b in bN if b%N == 0])%2 == a:
        pass
    else:
        bN.append(N)
    N -= 1

print(len(bN))
print(' '.join(bN))

### FIXED CODE ###

N = int(input())
aN = [ int(i) for i in input().split() ]
bN = [0] * N

for i in range(N, 0, -1):
    if sum(bN[i-1: :i]) % 2 != aN[i - 1]:
        bN[i-1] = 1

print(sum(bN))
if sum(bN) != 0:
    print(*[i+1 for i, b in enumerate(bN) if b == 1])
from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = deque([])
for i in range(n):
    P.append([[int(x) for x in input().split()]])
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

### FIXED CODE ###

def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            try :
                if isCLKWISE(phU) : break
                else : del phU[-2]
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            try :
                if isCLKWISE(phL) : break
                else : del phL[-2]
            except IndexError : break
    ph = phU + phL[1:-1]
    return ph
  
P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])
a,b,c,d = map(int,input().split())
A = a*c
B = a*d
if a<=0:
  if b>=0:
    C = 0
else:
  C = a*c
if c <=0:
  if d >=0:
    D = 0
else:
  D = a*c
E = b*c
F = b*d
print(max([A,B,C,D,E,F]))
    


### FIXED CODE ###

a,b,c,d = map(int,input().split())
A = a*c
B = a*d
if a<=0:
  if b>=0:
    C = 0
  else:
    C = a*c
else:
  C = a*c
if c <=0:
  if d >=0:
    D = 0
  else:
    D = a*c
else:
  D = a*c

E = b*c
F = b*d
print(max([A,B,C,D,E,F]))
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort(reverse = True)
# print(a)
ans = 0

def C(n, k, mod):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    x,y = 1,1
    while k > 0:
        x *= n
        y *= k
        n, k = n-1, k-1
        
    return x * pow(y, mod-2, mod) % mod


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1, mod)
    ans %= mod

a.reverse()
for i in range(0, n - k + 1):
    ans -= a[i] * C(n - i - 1, k - 1, mod)
    ans %= mod



print(ans)


### FIXED CODE ###

# import math
# import bisect
# import heapq
# from collections import deque
# import numpy as np

# a,b = map(int, input().split())
# n = int(input())
# p = list(map(int,input().split()))
c=input()


print(chr(ord(c) + 1))
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    X, Y, A, B, C = input_nums()
    P = input_nums()
    Q = input_nums()
    R = input_nums()
    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)
    res = []
    res += P[:X]
    res += Q[:Y]
    res.sort(reverse=True)
    index = 0
    maxindex = len(R)-1
    for i in range(len(res)):
        if res[i] < R[index] and index <= maxindex:
            res[i] = R[index]
            index += 1
    print(sum(res))
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    X, Y, A, B, C = input_nums()
    P = input_nums()
    Q = input_nums()
    R = input_nums()
    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort()

    P = sorted(P[:X])
    Q = sorted(Q[:Y])
    res = []
    res = P + Q + R
    res.sort(reverse=True)
    print(sum(res[:X+Y]))
if __name__ == '__main__':
    main()
import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-dict[i])

### FIXED CODE ###

import collections
N=int(input())
lst=input().split()
s=0
dic=collections.Counter(lst)
for i in dic.values():
    s+=(i*i-i)//2
for i in lst:
    print(s+1-dic[i])
N = int(input())
b = int(input())
c = int(input())
if N == 1:
  print("Hello World")
else:
  print(b+c)

### FIXED CODE ###

N = int(input())
if N % 2 == 1:
  print("Hello World")
else:
  a = int(input())
  b = int(input())
  print(a+b)
n = int(input())
sum=0

for i in range(1,n+1):
    if i % 15 == 0:
        print('Fizz Buzz')
    elif i % 3 == 0:
        print('Fizz')
    elif i % 5 == 0:
        print('Buzz')
    else:
		sum=sum+i

### FIXED CODE ###

n = int(input())
sum = 0

for i in range(1, n + 1):

    if i % 3 != 0 and i % 5 != 0:
        sum = sum + i

print(sum)
N=int(input())
S=str(input())
S=list(S)
ans=S.count('R')*S.count('G')*S.count('B')

for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=(j-i)+j-1
        if (S[i] != S[j]) and (S[j] != S[k]) and (S[k] != S[i]) :
            ans -= 1
print(ans)

### FIXED CODE ###

N=int(input())
S=str(input())
S=list(S)
ans=S.count('R')*S.count('G')*S.count('B')
for i in range(N): #判定を簡単にするためR:=1,G:=2,B:=4と置き換えておく
    if S[i]=='R':
        S[i]=1
    elif S[i]=='G':
        S[i]=2
    elif S[i]=='B':
        S[i]=4
for i in range(0,N-2):
    for j in range(i+1,N-1):
        k=(j-i)+j
        if k>N-1:
            continue
        if S[i]+S[j]+S[k] == 7 :
            ans -= 1
print(ans)
def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    r = a % b
    while r!=0:
      a = b
      b = r
      r = a % b
    return b
  
def main():
    K = int(input())
    list_ = []
    sum_ = 0
    for i in range(K):
        for j in range(K):
            a = gcd(i,j)
            list_.append(a)
    for i in list_:
        for j in range(K):
            a = gcd(i,j)
            sum_ += a
    print(sum_)

main()
  

### FIXED CODE ###

def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    r = a % b
    while r!=0:
      a = b
      b = r
      r = a % b
    return b
  
def main():
    K = int(input())
    list_ = []
    sum_ = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            a = gcd(i,j)
            list_.append(a)
    for i in list_:
        for j in range(1,K+1):
            a = gcd(i,j)
            sum_ += a
    print(sum_)

main()
import sys
input = sys.stdin.readline
h,n = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

D = [float("inf")] * (h+10**4+3)
D[0] = 0
for j in range(n):
    for i in range(len(D)//A[j][0] + 1):
        D[i] = min(D[i],D[i-A[j][0]] + A[j][1])
    # print(D[:20])
# print(D[:20])
print(min(D[h:]))

# a = float("inf")
# for i in range(n):
#     for j in range(n):
#         for k in range(h//A[i][0]+1):
#             b = A[i][1] * k + A[j][1] * max(0,-((-h+k*A[i][0])//A[j][0]))
#             a = min(a,b)
#             print(A[i][1] , k , A[j][1] , max(0,-((-h+k*A[i][0])//A[j][0])))
#             print(i,j,k,a)
        
# print(a)

# for i in range(n):
#     A[i].append(A[i][0]/ A[i][1])
# A.sort(reverse=True)
# A.sort(key=lambda x:x[2], reverse=True)
# print(A)
# a = 0
# while h > 0:
#     i=0
#     k = h//A[i][0]
#     h -= k * A[i][0]
#     a += k * A[i][1]
#     print(h)
#     if h > 0:
#         for i in range(n):
#             A[i][0] = min(A[i][0], h)
#             A[i][2] = A[i][0] / A[i][1]
#         A.sort(reverse=True)
#         A.sort(key=lambda x:x[2], reverse=True)
#     print(A)
# print(a)


### FIXED CODE ###

import sys
input = sys.stdin.readline
h,n = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n)]

D = [float("inf")] * (h+10**4+3)
D[0] = 0
for j in range(n):
    for i in range(len(D)):
        D[i] = min(D[i],D[i-A[j][0]] + A[j][1])
    # print(D[:20])
# print(D[:20])
print(min(D[h:]))

# a = float("inf")
# for i in range(n):
#     for j in range(n):
#         for k in range(h//A[i][0]+1):
#             b = A[i][1] * k + A[j][1] * max(0,-((-h+k*A[i][0])//A[j][0]))
#             a = min(a,b)
#             print(A[i][1] , k , A[j][1] , max(0,-((-h+k*A[i][0])//A[j][0])))
#             print(i,j,k,a)
        
# print(a)

# for i in range(n):
#     A[i].append(A[i][0]/ A[i][1])
# A.sort(reverse=True)
# A.sort(key=lambda x:x[2], reverse=True)
# print(A)
# a = 0
# while h > 0:
#     i=0
#     k = h//A[i][0]
#     h -= k * A[i][0]
#     a += k * A[i][1]
#     print(h)
#     if h > 0:
#         for i in range(n):
#             A[i][0] = min(A[i][0], h)
#             A[i][2] = A[i][0] / A[i][1]
#         A.sort(reverse=True)
#         A.sort(key=lambda x:x[2], reverse=True)
#     print(A)
# print(a)
N, M = map(int, input().split())
list=[]
s=[]
if N == 1:
    a, *b=map(int, input().split())
    print(a)
else:
    for i in range(N):
        list.append(input().split())
        s &= set(list[1:])
        list=[]
    print(len(s)) 

### FIXED CODE ###

N, M = map(int, input().split())
list=[]
s=set(range(1, M+1))
for i in range(N):
    K, *A = map(int, input().split())
    s &= set(A)
print(len(s))
import math

A,B,H,M = map(int,input().split())
s = 60*H+M
a = s*0.5
b = M*6
theta = 0

if abs(a-b)<=180:
    theta = abs(a-b)
else:
    theta = 360- abs(a-b)

C=A*A+B*B−2*A*B*math.cos(math.radians(abs(a-b)))
print(math.sqrt(C))


### FIXED CODE ###

import math
 
A,B,H,M = map(int,input().split())
s = 60*H+M
a = s*0.5
b = M*6
theta = 0
 
if abs(a-b)<=180:
    theta = abs(a-b)
else:
    theta = 360- abs(a-b)

C=(A*A)+(B*B)-(2*A*B)*math.cos(math.radians(abs(a-b)))
print(math.sqrt(C))
N=input()
print(180*(N-2))

### FIXED CODE ###

N=int(input())
print((180*(N-2)))
N = int(input())

if N% == 0:
  print((N//2)**2)
else:
  print(((N+1)//2)*((N-1)//2))

### FIXED CODE ###

N = int(input())

if N %2 == 0:
  print((N//2)**2)
else:
  print( ((N+1)//2) * ((N-1)//2) )
D = map(int, input().split())
c = list(map(int, input().split()))
s = []
for _ in range(D):
  s.append(list(map(int, input().split())))

lasts = [0 for i in range(len(c))]
ans = 0
for d in range(1, D+1):
  t = int(input()) - 1
  lasts[t] = d
  ans += s[d][t]
  for i in range(len(c)):
    ans -= c[i] * (d - lasts[i])
print(ans)

### FIXED CODE ###

D = int(input())
c = list(map(int, input().split()))
s = [[]]
for _ in range(D):
  s.append(list(map(int, input().split())))

lasts = [0 for i in range(len(c))]
ans = 0
for d in range(1, D+1):
  t = int(input()) - 1
  lasts[t] = d
  ans += s[d][t]
  for i in range(len(c)):
    ans -= c[i] * (d - lasts[i])
  print(ans)
a,b,c = map(int,input().split)

if a==b+c:
  print("Yes")
elif b==a+c:
  print("Yes")
elif c==a+b:
  print("Yes")

print("No")
      
        

### FIXED CODE ###

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

if a==b+c:
  print("Yes")
elif b==a+c:
  print("Yes")
elif c==a+b:
  print("Yes")
else:
  print("No")
s=input()
if a in s and b in s and c in s:
  print "Yes"
else:
  print "No"

### FIXED CODE ###

s=raw_input()
sa=0
sb=0
sc=0
for i in range(len(s)):
  if s[i]=="a":
    sa+=1
  if s[i]=="b":
    sb+=1
  if s[i]=="c":
    sc+=1
if sa==1 and sb==1 and sc==1:
    print "Yes"
else: 
    print "No"