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

n = int(input())
s = []
for _ in range(n):
    s.append(sorted(input()))
count = 0
for i in range(n):
    for j in range(i+1, n):
        if s[i] == s[j]:
            count += 1
print(count)

### FIXED CODE ###

import collections
n = int(input())
d = collections.defaultdict(int)
for _ in range(n):
    a = sorted(input())
    s = ''.join(a)
    d[s] += 1
count = 0
for v in d.values():
    count += v * (v-1) // 2
print(count)
### BUGGY CODE ###

def main(): 
    
    S = input()
    stack = []
    
    strs = S
    cmps = ["dream", "dreamer", "erase", "eraser"]

    while(1):
        if not cmps:
            if stack:
                strs, cmps = stack.pop()
            else:
                print("NO")
                return

        cmp_i = cmps.pop()
        if strs[:len(cmp_i)] == cmp_i:
            if cmps:
                stack.append((strs, cmps))

            strs = strs[len(cmp_i):]
            if strs == "":
                print("YES")
                return
            else:
                cmps = ["dream", "dreamer", "erase", "eraser"]

if __name__ == "__main__":
    main()
    


        


### FIXED CODE ###

from collections import deque

def main():
    divide = ["dream", "dreamer", "erase", "eraser"]

    S = input()

    q = deque([0])

    while(q):
        beg_i = q.popleft()

        if beg_i == len(S):
            print("YES")
            return
        
        for div_i in divide:
            end_i = beg_i + len(div_i)
            if S[beg_i:end_i] == div_i:
                q.append(end_i)
    
    print("NO")
    return

main()
### BUGGY CODE ###

import fractions


from functools import reduce
K=int(input())

def gcd_list(numbers):
  return reduce(fractions.gcd, numbers)


count=0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i==j and j==k and k==i:
        n=1
      elif i==j or j==k or k==i:
        n=3
      else:
        n=6
      count+=n*gcd_list([i,j,k])

print(count)

### FIXED CODE ###

import math

from functools import reduce
K=int(input())

def gcd_list(numbers):
  return reduce(math.gcd, numbers)


count=0
for i in range(1,K+1):
  for j in range(i,K+1):
    for k in range(j,K+1):
      if i==j and j==k and k==i:
        n=1
      elif i==j or j==k or k==i:
        n=3
      else:
        n=6
      count+=n*gcd_list([i,j,k])

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

S = input()
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]

for query in QUERY:
    #print(query)
    if query[0] == "1":#反転
        S = S[::-1]
    else:#=="2"
        if query[1] == "1":
            S = query[2] + S
        else:#=="2"
            S += query[2]
print(S)


### FIXED CODE ###

from collections import deque


S = deque(input())
Q = int(input())
QUERY = [input().split(" ") for i in range(Q)]
reverse_f = 0

for query in QUERY:
    if query[0] == "1":#反転
        reverse_f = (reverse_f+1)%2
    else:#=="2"
        if query[1] == "1":
            if reverse_f:
                S.append(query[2])
            else:
                S.appendleft(query[2])

        else:#=="2"
            if reverse_f:
                S.appendleft(query[2])
            else:
                S.append(query[2])

if reverse_f:
    S.reverse()
print("".join(list(S)))
### BUGGY CODE ###

N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn==M-ab[0]-i:
                break
            if D[M-ab[0]-i]==0:
                D[M-ab[0]-i]+=1
                pay+=ab[1]
                flag=False
                break
            else:
                i+=D[M-ab[0]-i]

        if flag:
            mn=M-ab[0]
            
print(pay)


### FIXED CODE ###

N,M=(int(x) for x in input().split())
L=[]
D=[0]*M

for i in range(N):
    L.append(tuple(int(x) for x in input().split()))

L = sorted(L, key=lambda x:-x[1])
pay=0
mn=-1
for ab in L:
    flag=True
    if ab[0]<=M and mn<M-ab[0]:
        i=0
        while True:
            if M-ab[0]-i<0:
                break
            if mn>M-ab[0]-i:
                break
            D[M-ab[0]-i]+=1
            if D[M-ab[0]-i]==1:
                pay+=ab[1]
                flag=False
                break
            else:
                if i==1:
                    i+=1
                else:
                    i+=D[M-ab[0]-i]-1
            
        if flag:
            mn=M-ab[0]
            
print(pay)
### BUGGY CODE ###

a, b, c = map(int, input().split())
array = []
for i in range(c):
	array.append(int(input()))
 
point = [b] * a
 
for i in range(c):
	for j in range(len(point)):
		if j+1 != int(array[i]):
			point[j] = point[j] -1
            
for i in range(len(point)):
	if point[i] > 0:
		print('Yes')
	else:
		print('No')

### FIXED CODE ###

a, b, c = map(int, input().split())
array = []
for i in range(c):
	array.append(int(input()))

point = [b] * a
 
for i in range(c):
	point[array[i]-1] = point[array[i]-1] + 1
            
for i in range(len(point)):
	if (point[i]-c) > 0 :
		print('Yes')
	else:
		print('No')
### BUGGY CODE ###

n=int(input())
s=[sorted(input())]
c=0
for i in range(n-1):
    a=sorted(input())
    c+=s.count(a)
    s.append(a)
print(c)

### FIXED CODE ###

import collections
n = int(input())
x = [''.join(sorted(input())) for _ in range(n)]
a = collections.Counter(x)
print(sum(i * ~-i // 2 for i in a.values()))
### BUGGY CODE ###

while 1:
    n = input()
    if n==0: break
    s = [0 for i in xrange(7)]
    for i in range(n):
        age = input()
        s[min(6, age/10)] += 1
    for i in xrange(7):
        print s[i]

### FIXED CODE ###

while 1:
    n = input()
    if n==0: break
    s = [0 for i in range(13)]
    for i in range(n):
        s[int(raw_input())/10] += 1
    for i in range(6):
        print s[i]
    print sum(s[6:])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import defaultdict
from bisect import bisect_left

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

# 部分和DPを変形させて、その値になるのに使われた値の集合を持っておく
dp = defaultdict(list)
dp[0].append(0)
for i in range(N):
    for j in range(K-1, -1, -1):
        if len(dp[j]):
            dp[j+A[i]] += dp[j]
            dp[j+A[i]].append(A[i])

# 和がK未満の集合はこの後のチェックで使わないので削る
dp = sorted(dp.items())
keys, lists = zip(*dp)
idx = bisect_left(keys, K)
keys = keys[idx:]
lists = lists[idx:]
sets = [set() for i in range(len(lists))]
for i, li in enumerate(lists):
    sets[i] = set(li)

ans = 0
for i in range(N):
    for k, s in zip(keys, sets):
        # A[i]減らしたらK未満になる状況で、一度でもA[i]が使われていれば必要
        if k-A[i] < K and A[i] in s:
            break
    else:
        # 該当するどの集合でも、一度も使われていなければ不要
        ans += 1
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))
### BUGGY CODE ###

L,R = map(int,input().split())
minmod = 2019

for i in range(L,R,1):
    for j in range(i+1,R+1,1):
        minmod = min(minmod,i*j%2019)

print(minmod)

### FIXED CODE ###

L,R = map(int,input().split())
right = min(L+2019, R+1)
minimum = 2019

for i in range(L,right):
    for j in range(i+1,right):
         minimum = min(minimum,(i*j) % 2019)

print(minimum)
### BUGGY CODE ###

import itertools
n = int(input())
s = [int(i) for i in input()]
a = {i for i in itertools.combinations(s, 3)}

print(len(a))

### FIXED CODE ###

n = int(input())
s = input()

l = [str(i).zfill(3) for i in range(0,1000)]

ct = 0
for i in l:
  n0 = s.find(i[0])
  if n0==-1:
    continue
  n1 = s.find(i[1], n0+1)
  if n1==-1:
    continue
  n2 = s.find(i[2], n1+1)
  if n2!=-1:
    ct += 1
   
print(ct)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
p = [0] * 100005
for i in range(100005):
    p[i] += a.count(i - 1)
    p[i] += a.count(i)
    p[i] += a.count(i + 1)

print(max(p))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
p = [0] * 100005
for i in a:
    p[i] += 1

num = 0
for i in range(1, 100000):
    num = max(num, sum(p[i - 1: i + 2]))

print(num)
### BUGGY CODE ###

s = list(input())
ans = 0
for i in range(4,len(s)+1):
    for j in range(0,len(s)+1-i):
      d = s[j:j+i]
      l = ''.join(d)
      if int(l) % 2019 == 0:
        ans += 1
print(ans)

### FIXED CODE ###

S = input()
cnt = [0]*2019
cnt[0] = 1
n = 0
t = 1
for i in reversed(S):
    n += int(i)*t
    n %= 2019
    cnt[n] += 1
    t *= 10
    t %= 2019
print(sum(i*(i-1)//2 for i in cnt))
### BUGGY CODE ###

def string():
    s = input()
    q = int(input())
    while q > 0:
        t = list(input().strip().split())
        if int(t[0]) == 1:
            s = s[::-1]
        else:
            if int(t[1]) == 2:
                s += t[2]
            else:
                s = t[2] + s
        q -= 1
    print(s)
string()

### FIXED CODE ###

def string():
    s = input()
    q = int(input())
    l = ''
    r = ''
    re = False
    for _ in range(q):
        t = input().split()
        if t[0] == '1':
            re = not re
        else:
            if re:
                if t[1] == '1':
                    r = r + t[2]
                else:
                    l = t[2] + l
            else:
                if t[1] == '1':
                    l = t[2] + l
                else:
                    r = r + t[2]
    s = l + s + r
    if re:
        s = s[::-1]
    print(s)
string()
### BUGGY CODE ###

#! python3
# areas_on_the_cross_section_diagram.py

cross_section = input()
cross_section_height = [0]
for i in range(len(cross_section)):
    if cross_section[i] == '\\':
        cross_section_height.append(cross_section_height[i]-1)
    elif cross_section[i] == '_':
        cross_section_height.append(cross_section_height[i])
    elif cross_section[i] == '/':
        cross_section_height.append(cross_section_height[i]+1)

# 水たまりを探す
# 左から探す
puddles = []
width = len(cross_section_height)
i = 0
while i < width-2:
    # i とペアとなる高さ
    is_down = False
    for j in range(i+1, width):
        if cross_section_height[j] > cross_section_height[i]:
            i += 1
            break
        elif cross_section_height[j] < cross_section_height[i]:
            is_down = True
        else:
            if is_down:
                puddles.append([i, j])
            i = j
            break

        if j == width-1:
            i += 1

# 面積の計算
puddle_areas = []
for start, end in puddles:
    area = 0
    for i in range(start+1, end+1):
        if cross_section[i-1] == '_':
            area += cross_section_height[start] - cross_section_height[i]
        elif cross_section[i-1] == '/':
            area += cross_section_height[start] - cross_section_height[i] + 0.5
        else:
            area +=cross_section_height[start] - cross_section_height[i] -  0.5
    puddle_areas.append(int(area))


if len(puddle_areas) == 0:
    print("0\n0")
else:
    print(sum(puddle_areas))
    print(len(puddle_areas), ' '.join([str(x) for x in puddle_areas]))


### FIXED CODE ###

cross_section = input()

stack = []
areas_stack = []
area = 0
for i in range(len(cross_section)):
    c = cross_section[i]
    if c == '\\':
        stack.append(i)
    elif c == '/' and len(stack) != 0:
        j = stack.pop()
        a = i - j
        area += a
        while len(areas_stack) != 0 and areas_stack[-1][0] > j:
            a += areas_stack.pop()[1]
        areas_stack.append([j, a])

print(area)
if area == 0:
    print(0)
else:
    print(len(areas_stack), ' '.join([str(x[1]) for x in areas_stack]))
### BUGGY CODE ###

import numpy
h,w,m = map(int,input().split())
hight = [0]*h
width = [0]*w
matrix =[0]*h
for i in range(h):
    matrix[i] = [0]*w
for i in range(m):
    hi,wi = map(int,input().split())
    hight[hi-1] += 1
    width[wi-1] += 1
    matrix[hi-1][wi-1] += 1
max_vh = max(hight)
max_vw = max(width)
max_h = list()
max_w = list()
for i in range(len(hight)):
    if(hight[i] == max_vh):
        max_h.append(i)
for i in range(len(width)):
    if(width[i] == max_vw):
        max_w.append(i)
# print(max_h,max_w)
if(len(max_h)==0 and len(max_w)):
    print(hight[max_h[0]]+width[max_w[0]]-matrix[max_h[0]][max_w[0]])
elif(len(max_h)!=0 and len(max_w)==0):
    ans = 0
    for i in range(len(max_h)):
        ans = max(ans,hight[max_h[i]]+width[max_w][0]-matrix[max_h[i]][max_w][0])
    print(ans)
elif(len(max_h)==0 and len(max_w)!=0):
    ans = 0
    for i in range(len(max_w)):
        ans = max(ans,hight[max_h[0]]+width[max_w[i]]-matrix[max_h[0]][max_w[i]])
    print(ans)
else:
    ans = 0
    for i in range(len(max_h)):
        for j in range(len(max_w)):
            ans = max(ans,hight[max_h[i]]+width[max_w[j]]-matrix[max_h[i]][max_w[j]])
    print(ans)



### FIXED CODE ###

import sys
h,w,m = map(int,input().split())
hight = [0]*h
width = [0]*w
S = set()

for i in range(m):
    hi,wi = map(int,input().split())
    S.add((hi-1,wi-1))
    hight[hi-1] += 1
    width[wi-1] += 1

max_vh = max(hight)
max_vw = max(width)

max_h = [i for i in range(h) if hight[i] == max_vh]
max_w = [i for i in range(w) if width[i] == max_vw]
for i in max_h:
    for j in max_w:
        if not(i,j) in S:
            print(max_vh+max_vw)
            sys.exit()

print(max_vh+max_vw-1)
### BUGGY CODE ###

list1=[2]
list2=[]
for i in range(3,100000,2):
    flag=0
    for j in range(3,318):
        if i<j**2:
            break
        elif i%j==0:
            flag=1
            break
    #print(i,flag)
    if flag==0:
        list1.append(i)
        if (int((i+1)/2) in list1):
            list2.append(i)
#print(list1)
#print(list2)


N=int(input())
for k in range(N):
    A=input()
    A=A.rstrip().split(" ")
    A1=int(A[0])
    A2=int(A[1])
#print(A1,A2)
    cnt=0
    for l in list2:
        if A1<= l <=A2 :
            cnt+=1
    print(cnt)
    

### FIXED CODE ###

listS=[1]*100005
listS[0]=0
listS[1]=0
for i in range(2,100003):
    if listS[i]==1:
        for j in range(2*i,100000,i):
            listS[j]=0
list2017=[0]
for k in range(1,100001):
    if listS[k]==1 and listS[int((k+1)/2)]==1:
        list2017.append(list2017[k-1]+1)
    else:
        list2017.append(list2017[k-1])

N=int(input())
for x in range(N):
    l,m=map(int,input().split())
    print(list2017[m]-list2017[l-1])
### BUGGY CODE ###

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

s = sum(a)
ans = float('inf')
for i in range(1, n):
    x = sum(a[:i])
    y = s - x
    if abs(x-y) < ans:
        ans = abs(x-y)

print(ans)


### FIXED CODE ###

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

tmp = 0
sum_list = [0]
for i in range(n):
    tmp += a[i]
    sum_list.append(tmp)

diff = float('inf')
for i in range(1,n):
    diff = min(diff, abs(sum_list[-1]-2*sum_list[i]))

print(diff)
### BUGGY CODE ###

n,k=map(int,input().split())
H=["dammy"]+list(map(int,input().split()))
dp=[0]*(n+1)
for i in range(2,min(k+2,n+1)):
    dp[i]=min(dp[j]+abs(H[i]-H[j]) for j in range(1,i))
for i in range(k+2,n+1):
    dp[i] = min(dp[i-j]+abs(H[i]-H[i-j]) for j in range(1,k+1))
print(dp[n])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [0] * n
    for i, Hi in enumerate(H):
        if i == 0:
            continue
        s = max(0, i-k) # iがk以下かどうかで処理が変わる.
        dp[i] = min([dl + abs(hl - Hi) for dl, hl in zip(dp[s:i], H[s:i])])
    print(dp[-1])
main()
### BUGGY CODE ###

n,k = map(int,input().split())
s = list(map(int,input().split()))
ans = 0
for i in range(n):
  a = (sum(s[i:i+k])+k)/2
  if a > ans:
    ans = a
print(ans)  

### FIXED CODE ###

import numpy as np
n,k = map(int,input().split())
s = list(map(int,input().split()))
s = np.array(s)
ans =  np.sum(s[:k])
a = ans
for i in range(n-k):
  a = a - s[i] + s[i+k]
  if a > ans:
    ans = a  
print((ans+k)/2)
### BUGGY CODE ###

import collections
n = int(input())
A = list(map(int, input().split()))

def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return collections.Counter(r)

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

kb = 1
for k, v in fa.items():
    kb *= pow(k, v)

mod = 10**9+7
s = sum(pow(a, mod-2, mod) for a in A)
print(s*kb%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))
### BUGGY CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    array = [list(map(int,input().split())) for _ in range(q)]
    N = [0]*n

    for i in range(n):
        if S[i:i+2] == 'AC':
            N[i] = 1
    for l,r in array:
        print(sum(N[l-1:r-1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n,q = map(int, input().split())
    S = input()
    N = [0]*(n+1)

    for i in range(n):
        N[i+1] += N[i]
        if S[i:i+2] == 'AC':
            N[i+1] += 1
    for i in range(q):
        l,r = map(int,input().split())
        print(N[r-1]-N[l-1])


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

from collections import Counter as cnt
import copy
n = int(input())
s = input()

count = cnt(s)
num_rest = []
for i in range(n):
  count[s[i]] -= 1
  rest = 0
  for value in count.values():
    if value != 0:
      rest += 1
  num_rest.append(rest)
#print(num_rest)

checked = set()
total = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if s[i] + s[j] not in checked:
      checked.add(s[i] + s[j])
      total += num_rest[j]
print(total)

### FIXED CODE ###

n = int(input())
s = list(input())

def search(s, c, left):
  for idx in range(left, len(s)):
    if s[idx] == c:
      return idx
  return -1

total = 0
for keta1 in range(10):
  first_keta1 = search(s, str(keta1), 0)
  if first_keta1 == -1 or first_keta1 >= n-2:
    continue
  for keta2 in range(10):
    first_keta2 = search(s, str(keta2), first_keta1 + 1)
    if first_keta2 == -1 or first_keta2 >= n-1:
      continue
    for keta3 in range(10):
      first_keta3 = search(s, str(keta3), first_keta2 + 1)
      if first_keta3 != -1:
        total += 1
print(total)
### BUGGY CODE ###

import copy
n = int(input())
A = []
for i in range(n):
  a = int(input())
  A.append(a)
for i in range(n):
  A_ = copy.deepcopy(A)
  A_.pop(i)
  print(max(A_))

### FIXED CODE ###

n = int(input())
A = []
for i in range(n):
  a = int(input())
  A.append(a)
m = max(A)
c = A.count(m)

if len(set(A)) > 1:
	m2 = sorted(set(A))[-2]

bool = False
if c == 1:
  bool = True

for i in A:
  if bool and i==m:
    print(m2)
  else:
    print(m)
### BUGGY CODE ###

N,x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
count = 0

while a[0] > x:
    a[0] -= 1
    count += 1

for i in range(N-1):
    while a[i] + a[i+1] > x:
        a[i+1] -= 1
        count += 1
        
print(count)


### FIXED CODE ###

N,x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
count = 0

while a[0] > x:
    count += a[0] - x
    a[0] = x

for i in range(N-1):
    if a[i] + a[i+1] > x:
        count += a[i+1] - (x - a[i])
        a[i+1] = x - a[i]

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

h,n = map(int,input().split())
dp = [float("inf")]*(h+10001)
dp[0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[j] = min(dp[j],dp[j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[i])

print(ans)


### FIXED CODE ###

h,n = map(int,input().split())
dp = [[float("inf")]*(h+10001) for i in range(n+1)]
dp[0][0]=0

for i in range(n):
    a,b= map(int,input().split())

    for j in range(h+10001):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j-a]+b)
ans = float("inf")
for i in range(h,h+10001):
    ans = min(ans,dp[n][i])

print(ans)