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

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
L = [list(map(int,input().split())) for i in range(M)]
L = sorted(L, key=lambda x: x[1], reverse=True)

ans = 0

q = bisect.bisect(A,L[0][1])
ans += sum(A[q:])
A = A[:q]

for i in range(M) :
    b,c = L[i]
    
    bi = bisect.bisect(A,c)
    
    K = min(b,bi)
    ans += c*K
    A = A[K:]
ans += sum(A)
print(ans)
    

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
L = [list(map(int,input().split())) for i in range(M)]

P = sorted(([[1,A[i]] for i in range(N)] + L),key=lambda x: x[1],reverse=True)

ans = 0
rest = N

for cost,value in P :
    K = min(cost, rest)
    K = max(0,K)
    ans += K * value
    rest -= cost

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

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

f_inf = float("inf")
cost = [f_inf]*N

cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        if cost[i] > cost[i-k]+abs(H[i]-H[i-k]):
            cost[i] = cost[i-k]+abs(H[i]-H[i-k])

print(cost[N-1])


### FIXED CODE ###

# EDPC B Frog 2
N, K = map(int, input().split())
H = list(map(int,input().split()))

cost = [float("inf")]*N
cost[0] = 0
cost[1] = abs(H[1]-H[0])

for i in range(2,N):
    for k in range(1,min(K,i)+1):
        cost[i] = min(cost[i], cost[i-k]+abs(H[i]-H[i-k]))

print(cost[N-1])
### BUGGY CODE ###

import numpy as np

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1 = [[-1 for i in range(w)] for j in range(h)]
dp2 = [[-1 for i in range(w)] for j in range(h)]
dp3 = [[-1 for i in range(w)] for j in range(h)]
dp4 = [[-1 for i in range(w)] for j in range(h)]





for i in range(w):
    for j in range(h):
        if s[j][i] == "#":
            dp3[j][i] = 0
        elif j == 0:
            dp3[j][i] = 1
        else:
            dp3[j][i] = 1 + dp3[j-1][i]

        if s[h-j-1][i] == "#":
            dp4[h-j-1][i] = 0
        elif h-j-1 == h-1:
            dp4[h-j-1][i] = 1
        else:
            dp4[h-j-1][i] = 1 + dp4[h-j][i]


a = 1
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]
a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)

### FIXED CODE ###

h,w = map(int,input().split(" "))
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        s[i][j] = tmp[j]

dp1= []
dp2= [[-1 for i in range(w)] for j in range(h)]
dp3=[]
dp4=[[-1 for i in range(w)] for j in range(h)]


for i in range(h):
    dp1.append([])
    dp3.append([])
    for j in range(w):
        dp1[i].append(-1)
        dp3[i].append(-1)

        if s[i][j] == "#":
            dp1[i][j] = 0
        elif j == 0:
            dp1[i][j] = 1
        else:
            dp1[i][j] = 1 + dp1[i][j-1]

        if s[i][w-j-1] == "#":
            dp2[i][w-j-1] = 0
        elif w-j-1 == w-1:
            dp2[i][w-j-1] = 1
        else:
            dp2[i][w-j-1] = 1 + dp2[i][w-j]

        if s[i][j] == "#":
            dp3[i][j] = 0
        elif i == 0:
            dp3[i][j] = 1
        else:
            dp3[i][j] = 1 + dp3[i-1][j]

        if s[h-i-1][j] == "#":
            dp4[h-i-1][j] = 0
        elif h-i-1 == h-1:
            dp4[h-i-1][j] = 1
        else:
            dp4[h-i-1][j] = 1 + dp4[h-i][j]



        

a = 1
for i in range(h):
    for j in range(w):
        a = max(a,dp1[i][j]+dp2[i][j]+dp3[i][j]+dp4[i][j]-3)


print(a)
### BUGGY CODE ###

s = input()
t = input()

def func(s, t):
    for i, (a, b) in enumerate(zip(s, t)):
        while True:
            ss, tt = s[i + 1:], t[i + 1:]
            si = ss.find(a)
            ti = tt.find(b)
            if si != ti:
                return 'No'
            if si == -1:
                break
            i += si + 1
    return 'Yes'

ans = func(s, t)

print(ans)

### FIXED CODE ###

s = input()
t = input()

s2t = {}
t2s = {}
ans = 'Yes'
for si, ti in zip(s, t):
    if si not in s2t:
        s2t[si] = ti
    elif s2t[si] != ti:
        ans = 'No'
        break
    if ti not in t2s:
        t2s[ti] = si
    elif t2s[ti] != si:
        ans = 'No'
        break

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



def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, M = map(int, input().split())
    g = [[] for _ in range(N)] #場合によって変える
    
    for _ in range(M):
        x, y = map(int, input().split())
        g[x-1].append(y-1)
    dp = [0]*N
    
    def func(i):
        for j in g[i]:
            dp[j] = max(dp[j], dp[i]+1)
            func(j)

    for i in range(N):
        if dp[i]==0:
            func(i)
    print(max(dp))


if __name__ == '__main__':
    main()

### FIXED CODE ###

#トポロジカルソートなるもの
#再帰で書いてるところをwhileで書いてる
#要は無駄な探索(再帰呼び出し)を無くしてる
#まぁ思いつかない

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    n,m = map(int,input().split())
    edge = [[] for i in range(n)]
    #st:入る辺が無い頂点
    st = []
    #to[i]:頂点iに入る辺数
    to = [0]*n
    for i in range(m):
        x,y = map(int, input().split())
        edge[x-1].append(y-1)
        to[y-1] += 1
    for i in range(n):
        if to[i] == 0:
            st.append(i)

    #dp[i]:頂点iを終点とする最長のパスの長さ
    dp = [0]*n
    while st:
        go = st.pop()
        for e in edge[go]:
            to[e] -= 1
            if to[e] == 0:
                st.append(e)
            dp[e] = max(dp[e],dp[go]+1)
    print(max(dp))


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

# -*- coding: utf-8 -*-
import numpy as np
N, X, Y = list(map(int, input().split()))

distance_lis = np.zeros(N-1, dtype=np.int32)
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        # XYを使わない場合
        a = j - i
        b = np.abs(X - i) + np.abs(Y - j) + 1
        distance = min(a, b)
        distance_lis[distance-1] += 1
for dis in distance_lis:
    print(dis)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
N, X, Y = list(map(int, input().split()))

distance_lis = [0]*(N-1)
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        # XYを使わない場合
        a = j - i
        b = abs(X - i) + abs(Y - j) + 1
        distance = min(a, b)
        distance_lis[distance-1] += 1
for dis in distance_lis:
    print(dis)
### BUGGY CODE ###

N,C = map(int,input().split())
X = [0]*N
V = [0]*N
XX = [0]*N
VV = [0]*N
for i in range(N):
    X[i],V[i] = map(int,input().split())
    XX[N-i-1] = C-X[i]
    VV[N-i-1] = V[i]
from numpy import array as arr
X = arr(X)
V = arr(V)
XX = arr(XX)
VV = arr(VV)
a = []
b = []
for i in range(N):
    x = X[i]
    v = V[:i+1].sum()
    xx = XX[i]
    vv = VV[:i+1].sum()
    a.append(v-x)
    b.append(vv-xx)
aa = arr([0]*N)
bb = arr([0]*N)
for i in range(N):
    aa[i] = max(a[:i+1])
    bb[i] = max(b[:i+1])
for i in range(N-1):
    x = 2*(C-X[-i-1])
    v = V[-i-1:].sum()
    xx = 2*(C-XX[-i-1])
    vv = VV[-i-1:].sum()
    a.append(v-x+aa[N-i-2])
    b.append(vv-xx+bb[N-i-2])
a.append(0)
print(max(max(a),max(b)))

### FIXED CODE ###

N,C = map(int,input().split())
x1=[]
v1=[]

for i in range(N):
    x,v = map(int,input().split())
    x1.append(x)
    v1.append(v)
x2 = [C-x for x in x1]
v2 = [v for v in v1]
x2.reverse()
v2.reverse()

res1 = 0
res2 = 0
s1 = 0
s2 = 0
r1 = [0]
r2 = [0]
for i in range(N):
    s1 += v1[i]
    s2 += v2[i]
    res1 = max(res1,s1-x1[i])
    res2 = max(res2,s2-x2[i])
    r1.append(res1)
    r2.append(res2)

vl1 = [0]*(N+1)
vl2 = [0]*(N+1)
for i in range(N):
    vl1[i+1] = v2[i]+vl1[i]
    vl2[i+1] = v1[i]+vl2[i]
for i in range(N):
    vl1[i+1] -= 2*x2[i]
    vl2[i+1] -= 2*x1[i]



ans = 0
for i in range(N+1):
    res = vl1[i]+r1[N-i]
    if res > ans:
        ans = res
    res = vl2[i]+r2[N-i]
    if res > ans:
        ans = res

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

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

p = list(map(int, input().split()))
hope_list = []

for i in p:
    hope_list.append((i+1)*0.5)

max = 0
for j in range(n-k+1):
    b = hope_list[j:j+k]
    goukei = sum(hope_list[j:j+k])
    if goukei > max:
        max = goukei

print(max)

### FIXED CODE ###

import numpy as np

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

p = np.array(list(map(int, input().split())))


index = 0
goukei = sum(p[0:k])
max = goukei
for j in range(n-k):
    goukei = (goukei - p[j] + p[j+k])
    if goukei > max:
        max = goukei
        index = j+1

ans = 0
for i in range(index, index+k):
    ans += ((p[i]+1)*0.5)

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

from collections import defaultdict
N, S = map(int, input().split())
A = tuple(map(int, input().split()))

mod = 998244353
U = 3000

pow2 = [1] * (U + 1)
for i in range(1, U + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

dp = defaultdict(int)
dp[(0, 0)] = 1
ans = 0
for a in A:
    newDP = defaultdict(int)
    for (sm, cnt), v in dp.items():
        # 追加しない
        newDP[(sm, cnt)] += v
        newDP[(sm, cnt)] %= mod
        # 追加する
        newDP[(sm+a, cnt + 1)] += v
        newDP[(sm+a, cnt + 1)] %= mod
    dp = newDP

ans = 0
for i in range(N + 1):
    ans = (ans + pow2[N - i] * dp[(S, i)]) % mod
print(ans)


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
fft = np.fft.rfft
ifft = np.fft.irfft
mod = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))
U = 3003

dp = np.zeros(U+10, dtype=np.int64)
dp[0] = 1
for a in A:
    newDP = dp.copy() * 2
    newDP[a:] += dp[:-a]
    newDP %= mod
    dp = newDP

print(dp[S])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  b.append(a.index(i+1)+1)
print(" ".join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [None] * n 
for i in range(n):
  b[a[i]-1] = i+1
print(" ".join(map(str, b)))
### BUGGY CODE ###


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

    lst = [0 for i in range(n*3)]
    for i in range(n):
        lst[3*i] = a[i]
        lst[3*i+1] = a[i]+1
        lst[3*i+2] = a[i]+2

    ans = -1
    for i in set(lst):
        ans = max(lst.count(i),ans)

    print(ans)



if __name__ == "__main__":
        main()


### FIXED CODE ###


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

    #lst = [0 for i in range(n*3)]
    ans_lst = [0 for i in range(max(a)+4)]
    """
    for i in range(n):
        lst[3*i] = a[i]
        lst[3*i+1] = a[i]+1
        lst[3*i+2] = a[i]+2
    """

    for i in a:
        ans_lst[i] += 1
        ans_lst[i+1] += 1
        ans_lst[i-1] += 1

    """
    ans = -1
    for i in set(lst):
        ans = max(lst.count(i),ans)
    """

    print(max(ans_lst))


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

N = int(input())
HN = list(map(int, input().split(" ")))

Max = 0

i = 0
while i < (N - 1):
    Count = 0
    NowHeight = HN[i]
    for j in range(i+1, N):
        NextHeight = HN[j]
        if NowHeight >= NextHeight:
            NowHeight = NextHeight
            Count = Count + 1
        else:
            break
    if Count > Max:
        Max = Count
        i = i + 1 + Count
    else:
        i = i + 1

print(Max)

### FIXED CODE ###

N = int(input())
HN = list(map(int, input().split(" ")))
 
Max = 0
 
i = 0
while i < (N - 1):
    Count = 0
    NowHeight = HN[i]
    for j in range(i+1, N):
        NextHeight = HN[j]
        if NowHeight >= NextHeight:
            NowHeight = NextHeight
            Count = Count + 1
        else:
            break
    if Count > Max:
        Max = Count
    i = i + 1 + Count
 
print(Max)
### BUGGY CODE ###

n=int(input())
l=[int(i) for i in input().split()]
if len(set(l))==1:
    print(n//2)
    exit()
even=[l[i] for i in range(n) if i%2==0]
odd=[l[i] for i in range(n) if i&1]
from collections import Counter 
c1=Counter(even)
c2=Counter(odd)
a=[i for i in c1]
b=[i for i in c2]
maxi=max(c1.values())
maxi=max(maxi,max(c2.values()))
for a1 in a: 
    for b1 in b: 
        if a1==b1:
            continue 
        maxi=max(maxi,c1[a1]+c2[b1])
print(n-maxi)

### FIXED CODE ###

n=int(input())
l=[int(i) for i in input().split()]
if len(set(l))==1:
    print(n//2)
    exit()
even=[l[i] for i in range(n) if i%2==0]
odd=[l[i] for i in range(n) if i&1]
from collections import Counter 
c1=Counter(even)
c2=Counter(odd)
a=[i for i in c1]
b=[i for i in c2]
maxi=max(c1.values())
maxi=max(maxi,max(c2.values()))
a.sort(key=lambda x:-c1[x])
b.sort(key=lambda x:-c2[x])
for a1 in a: 
    for b1 in b: 
        if a1==b1:
            continue 
        maxi=max(maxi,c1[a1]+c2[b1])
        break 
print(n-maxi)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

ans = []
for x in range(X):
    if x >= K:
        break
    for y in range(Y):
        if x + y >= K:
            break
        for z in range(Z):
            if x + y + z >= K:
                break

            value = A[x] + B[y] + C[z]
            ans.append(value)

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])


### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())),reverse=True)
B = sorted(list(map(int, input().split())),reverse=True)
C = sorted(list(map(int, input().split())),reverse=True)

ans = []
for x in range(X):
    if x+1 > K:
        break
    for y in range(Y):
        if (x+1) * (y+1) > K:
            break
        for z in range(Z):
            if (x+1) * (y+1) * (z+1) > K:
                break

            value = A[x] + B[y] + C[z]
            ans.append(value)

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

def set_range(x, y):
    return {t+x for t in range(y-x)}

N, M =  map(int, input().split()) 
L = [0]*M
R = [0]*M

for m in range(M):
    L[m], R[m] = map(int, input().split())

S = set_range(1, N+1)
for m in range(M):
    S = S.intersection(set_range(L[m], R[m]+1))
    
print(len(S))

### FIXED CODE ###

N, M =  map(int, input().split()) 
L = [0]*M
R = [0]*M

for m in range(M):
    L[m], R[m] = map(int, input().split())
    
print(max(0,min(R)-max(L)+1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def bellman_ford(s, n, G, st):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if not y in st:
                continue
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    for _ in range(m):
        a, b, c = map(int, input().split())
        G.append([a-1, b-1, -c+p])
        U[b-1].append(a-1)
    st = set()
    st.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st:
                q.append(v)
                st.add(v)
    ans = bellman_ford(0, n, G, st)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def bellman_ford(s, n, G):
    d = [float('inf')]*n
    d[s] = 0
    for i in range(n):
        update = False
        for x, y, z in G:
            if d[y] > d[x] + z:
                d[y] = d[x] + z
                update = True
        if not update:
            break
        if i == n - 1:
            return None
    return d

def main():
    n, m, p = map(int, input().split())
    G = []
    U = [[] for _ in range(n)]
    V = [[] for _ in range(n)]
    dic = {}
    for _ in range(m):
        a, b, c = map(int, input().split())
        if (a-1, b-1) in dic:
            if dic[(a-1, b-1)] > -c+p:
                dic[(a-1, b-1)] = -c+p
        else:
            dic[(a-1, b-1)] = -c+p
    for v in dic.keys():
        G.append([v[0], v[1], dic[v]])
        U[v[1]].append(v[0])
        V[v[0]].append(v[1])
    st1 = set()
    st1.add(n-1)
    q = [n-1]
    while len(q) > 0:
        t = q.pop(-1)
        for v in U[t]:
            if not v in st1:
                q.append(v)
                st1.add(v)
    st2 = set()
    st2.add(0)
    q = [0]
    while len(q) > 0:
        t = q.pop(-1)
        for v in V[t]:
            if not v in st2:
                q.append(v)
                st2.add(v)
    st = st1 & st2
    eg = []
    for v in G:
        if v[0] in st and v[1] in st:
            eg.append(v)
    ans = bellman_ford(0, n, eg)
    if ans is None:
        print(-1)
    else:
        print(max(0, -ans[n-1]))

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

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

ans = 0
for s in sorted(set(a))[::-1]:
    cnt = a.count(s)
    tmp = cnt - s
    ans += (tmp > 0) * tmp + (tmp < 0) * cnt
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
ans = 0
for k, v in cnt.items():
    if k > v:
        ans += v
    elif k < v:
        ans += (v-k)
print(ans)
### BUGGY CODE ###

def abc175_c_1():
    x, k, d = map(int, input().split())

    def solve(x, k, d):
        # Xを絶対値でプラスの値にし、0に近づける問題に置き換える
        x = abs(x)

        # (x // d)は0の手前まで移動するのに必要な回数。kの方が小さい場合はk回移動してしまえばよい
        if k < (x // d):
            return x - (k * d)
        # kのほうが大きい場合はそこから数回移動が必要
        else:
            # xからとりあえずx//d回は移動してOK
            current_x = x - d * (x // d)
            k = k - (x // d)
            
            # 結局ここが時間がかかるので終わらない。
            for i in range(k):
                current_x = min(abs(current_x + d), abs(current_x - d))
            return current_x

    ans = solve(x, k, d)
    print(ans)

if __name__ == '__main__':
    abc175_c_1()

### FIXED CODE ###

def abc175_c_1():
    x, k, d = map(int, input().split())

    def solve(x, k, d):
        # Xを絶対値でプラスの値にし、0に近づける問題に置き換える
        x = abs(x)

        # (x // d)は0の手前まで移動するのに必要な回数。kの方が小さい場合はk回移動してしまえばよい
        if k < (x // d):
            return x - (k * d)
        # kのほうが大きい場合はそこから数回移動が必要
        else:
            # xからとりあえずx//d回は移動してOK
            current_x = x - d * (x // d)
            k = k - (x // d)

            # 結局ここが時間がかかるので終わらない。(10**15回とか探索しちゃう。)

            if (k % 2) == 0:
                # 残りの移動回数が偶数回なら移動を繰り返してその場所に戻ってくる
                return current_x
            else:
                # 奇数回の場合、偶数回移動を繰り返した後、もう一回だけ移動する。
                # return min(abs(current_x + d), abs(current_x - d))
                return abs(current_x - d)

    ans = solve(x, k, d)
    print(ans)

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

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

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in ansListab:
  for j in c:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])


### FIXED CODE ###

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

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ansListab=[]
for i in range(x):
  for j in range(y):
    ansListab.append(a[i]+b[j])

ansListab.sort(reverse= True)

if len(ansListab)>k:
  ansListab=ansListab[0:k]

ansList=[]

for i in c:
  for j in ansListab:
    ansList.append(i+j)

ansList.sort(reverse= True)

for i in range(k):
  print(ansList[i])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = []
for i in range(N):
    for j in range(N):
        if A[j] == i+1:
            answer.append(j+1)
print(' '.join(map(str, answer)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = {}
for i in range(N):
    B[A[i]] = i+1
answer = sorted(B.items())
ac=[]
for i in range(N):
    ac.append(answer[i][1])
print(' '.join(map(str, ac)))
### BUGGY CODE ###

total = 0
A = int(input())
B = []
for i in range(A):
    C = list(input())
    C.sort()
    B.append("".join(C))
for i in range(A):
    D = B[i]
    for j in range(A-i-1):
        if D == B[i+1+j]:
            total += 1
print(total)

### FIXED CODE ###

import collections
from math import factorial
A = int(input())
listA = []
total = 0
listB = {}
for i in range(A):
    B = list(input())
    B.sort()
    listA.append("".join(B))
for i in listA:
    if i in listB:
        listB[i] += 1
        total += listB[i]-1
    else:
        listB[i] = 1
print(total)
### BUGGY CODE ###

h, n= list(map(int,input().split()))
a = []
b = []
for i in range(n):
    a_in, b_in = list(map(int,input().split()))
    a.append(a_in)
    b.append(b_in)

if h == 1:
    print(min(b))
else:
    dp = [0]*h
    dp[0] = min(b)
    for i in range(2,h+1):
        c = [0]*n
        for j in range(n):
            if i > a[j]:
                c[j] = b[j] + dp[i-a[j]-1]
            else:
                c[j] = b[j]
        dp[i-1] = min(c)
    print(dp[h-1])


### FIXED CODE ###

h, n= list(map(int,input().split()))
a = []
b = []
for i in range(n):
    a_in, b_in = list(map(int,input().split()))
    a.append(a_in)
    b.append(b_in)

if h == 1:
    print(min(b))
else:
    dp = [0]*h
    dp[0] = min(b)
    for i in range(2,h+1):
        c = [0]*n
        for j in range(n):
            if i > a[j]:
                c[j] = b[j] + dp[i-a[j]-1]
            else:
                c[j] = b[j]
        dp[i-1] = min(c)
    print(dp[h-1])