Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
#        for line in sys.stdin:
#            lines.append(line)
        lines.append(input())
        (h, n) = [int(e) for e in lines[0].split(" ")]
        for _ in range(n):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        (h, n) = [int(e) for e in lines[0].split(" ")]
    
    ab = []
    for i in range(1, n+1):
        (c, d) = [int(e) for e in lines[i].split(" ")]
        ab.append((c, d))


    return (h, n, ab)

def solve(h, n, ab):


    abc = [(a, b, a / b) for a, b in ab]
    abc.sort(key = lambda e: (-e[2], e[1]))

    # 効率よくてもMP小さくても
    # オーバースペックな魔法はだめ。

    a = abc[0][0]
    b = abc[0][1]
    c = abc[0][2]
    if debug:
        log("a=%d, b=%d, c=%f" % (a, b, c))
    cnt = h // a
    remain = h % a

    abc2 = [e[1] for e in abc if e[1] < b and e[0] >= remain]
    if abc2:
        b2 = min(abc2)
    else:
        b2 = b

    result = cnt * b + b2


    return result

def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r)
    else:
        print("%s" % result)

if __name__ == '__main__':

    main()

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = []
for _ in range(N):
    Ai, Bi = map(int, input().split())
    AB.append([Ai, Bi, float(Ai)/float(Bi)])

sorted_AB = sorted(AB, key=lambda a:(a[2], -a[1]), reverse=True)

total = 0
i = 0
while H > 0:
    count = int(H/sorted_AB[i][0])
    if count == 0:
        count += 1
    H -= sorted_AB[i][0] * count
    total += sorted_AB[i][1] * count
    i += 1
    

print(total)

Submission status: Wrong Answer

Solution code:
import math

hp,n= map(int,input().split())
rc = [list(map(int,input().split())) for i in range(n)]

rchp=[]
rcmp=[]
li=[]

for i in rc:
    rchp.append(i[0])
    rcmp.append(i[1])
    li.append(i[0]/i[1])

idx = li.index(max(li))

ans1 = hp // rchp[idx]
nokori = hp %  rchp[idx]

print(ans1)
print(nokori)
print(ans1*rcmp[idx])

li2=[]

if nokori == 0:
    print(ans1 * rcmp[idx])
else:
    for j in rc:
        if nokori <= j[0]:
            li2.append(j[1])
        else:
            li2.append(math.ceil(nokori/j[0]) * j[1])
    print(ans1 * rcmp[idx] + min(li2))

Submission status: Wrong Answer

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

import pdb
import sys
sys.setrecursionlimit(10**7)
F = sys.stdin

H,N = map(int,F.readline().split())
b_a_dict = {}
efficiency_b_dict = {}
ans = 0
for n in range(N):
    a1, b1 = map(int,F.readline().split())
    efficiency = a1/b1
    if efficiency in efficiency_b_dict:
        efficiency_b_dict[efficiency] = min(efficiency_b_dict[efficiency], b1)
    else:
        efficiency_b_dict[efficiency] = b1

    if b1 in b_a_dict:
        b_a_dict[b1] = max(a1, b_a_dict[b1])
    else:
        b_a_dict[b1] = a1

efficiency_b_dict_sorted = sorted(efficiency_b_dict.items(), key=lambda x:-x[0])
zantei_kougeki = 100000
zantei_ans = []
for ef in efficiency_b_dict_sorted:
    print(ef)
    b = ef[1]
    a = b_a_dict[b]
    if H >= a:
        if H % a == 0:
            plus = min((H / a) * b, zantei_kougeki)
            ans += plus
            zantei_ans.append(ans)
        ans += (H // a) * b
        H = H - (H * a)

    if H < a:
        zantei_ans.append(ans + b)
        zantei_kougeki = b

ans = min(zantei_ans)

print(int(ans))

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

list = [list(map(int, input().split())) for _ in range(n)]  

for i in range(len(list)):
  cospa = list[i][0] / list[i][1]
  list[i].append(cospa)

list.sort(key=itemgetter(1)) #リスト1は2次元以の配列
list.sort(key=itemgetter(2), reverse = True) #リスト1は2次元以の配列

mp = 0
for i in range(n):
  while h >= list[i][0]:
    count = h // list[i][0]
    h = h - ((count) * list[i][0])
    mp += count * list[i][1]
    if not h <=0:
#      h -= list[i+1][0]
      mp += list[i+1][1]
print(mp)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

l=[]
ll=[]
for i in range(n):
 a,b=map(int,input().split())
 l.append(b/a)
 ll.append([a,b])

l_i=np.argsort(l)
ans=0
cnt=0
cnt+=h//ll[l_i[0]][0]
ans+=cnt*ll[l_i[0]][1]
z=h-cnt*ll[l_i[0]][0]


ll=sorted(ll,key=lambda x:x[1])
m=10**9
inx=-1
for lll in ll:
 if z%lll[0]==0:
  x=z//lll[0]
 else:
  x=z//lll[0]+1
 if x<m:
  m=x
  inx=lll[1]

print(ans+m*inx)

Submission status: Wrong Answer

Solution code:
# print('input >>')
H, N = map(int,(input().split()))
ABs = []
for _ in range(N):
    ABs.append(tuple(map(int,(input().split()))))

ABs.sort(key=lambda x: x[1])
ABs.sort(key=lambda x: x[0]/x[1], reverse=True)
ans = 0

print(ABs)
for AB in ABs:
    print(AB[0] / AB[1])
    if AB[0] <= H:
        times = H // AB[0]
    else:
        times = 1
    H -= AB[0] * times
    ans += AB[1] * times
    # print('times', times, 'H', H, 'damage', AB[1] * times, 'ans', ans)
    if H <= 0:
        break

# print('-----output-----')
print(ans)

# 分からん……貪欲法的アプローチではないんか……

Submission status: Wrong Answer

Solution code:
# 2020/01/26
# AtCoder Beginner Contest 153 - C

from operator import itemgetter

# Input
h, n = map(int,input().split())

ablist = list()
for i in range(n):
    l = list()
    a, b = map(int,input().split())
    efc = a / b
    l.append(a)
    l.append(b)
    l.append(efc)

    ablist.append(l)

# 効率の良い順にソート
ablist.sort(key=itemgetter(2))
ablist.reverse()

# Init
wk_h = h
usemp = 0
min_last_mp = 10 ** 9

# 最も効率的なものを使う
atcnt = wk_h // ablist[0][0]

# 最も効率的なもので2回以上かかる場合、最後の1回以外はそれを使う
if atcnt > 0:
    usemp = usemp + atcnt * ablist[0][1]
    wk_h = wk_h - atcnt * ablist[0][0]
    min_last_mp = ablist[0][1]

# 与える体力順にソート
ablist.sort(key=itemgetter(0))
ablist.reverse()

i = 1
if wk_h <= 0:
    ans = usemp
else:
    while(i < n and wk_h <= ablist[i][0]):
        atcnt = wk_h // ablist[i][0]
        wk_mp = 0
        if atcnt > 0:
            if wk_h % ablist[i][0] == 0:
                wk_mp = ablist[i][1] * atcnt
            else:
                wk_mp = ablist[i][1] * (atcnt + 1)
        else:
            wk_mp = ablist[i][1]
            
        if min_last_mp > wk_mp:
            min_last_mp = wk_mp
    
        i = i + 1
    
    ans = usemp + min_last_mp

# Output
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A= [(list(map(int, input().split()))) for _ in range(N)]
total_point = 0
 
while H > 0:
	B= [a[0]/a[1] for a in A]
	index = B.index(max(B))
 
	num = H//A[index][0]
	H = H%A[index][0]
	used_point = A[index][1]
	damage = A[index][0]
	A = [a for a in A if a[0]<damage and a[1]<used_point]
	if len(A) == 0:
		num += 1
		H = 0
	total_point += num*used_point
print(total_point)

Submission status: Wrong Answer

Solution code:
import sys



sys.setrecursionlimit(10 ** 7)

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

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

dp = [[10**9] * (H+1) for _ in range(N+1)]

for i in range(N):
    dp[i][0] = 0


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            m = min(dp[i+1][h-MAGIC[i][0]:])
            #print("num", h-MAGIC[i][0], dp[i][h-MAGIC[i][0]:])
            # print(m)
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            #print("ok", h)
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])

    # print(dp[i+1])

# print(dp)
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
f = lambda:map(int,input().split())

h, n = f()
l = []
for i in range(n):
  a, b = f()
  l.append([a,b,b/a])
l.sort(key=lambda x:x[2])
print(l)

ans = 0
for i in range(n):
  x = l[i][0]
  y = l[i][1]
  d = h//x
  h = h%x
  ans += d*y
  print(d, h, ans)
  if h == 0:
    break
if h > 0:
  la = 10**4
  for i in range(n):
    if h <= l[i][0]:
      la = min(la, l[i][1])
else:
  la = 0
print(ans+la)

Submission status: Wrong Answer

Solution 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)

C=[]
for i in range(n):
  c=A[i]/B[i]
  C.append(c)
m=C.index(max(C))

print(int(h/A[m]))

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
A = [0 for _ in range(N)]
B = [0 for _ in range(N)]
C = [0 for _ in range(N)]
Max=0
add=0
for i in range(N):
  A[i],B[i]=map(int,input().split())
  C[i]=A[i]/B[i]
  if Max<C[i]:
    Max=C[i]
    temp=i
l_2d=[A,B,C]
l_2d_t = [list(x) for x in zip(*l_2d)]
l_2d_t.sort(key=lambda x : x[1])
kaisu=H//A[temp]
H=H-A[temp]*kaisu
if H !=0:
  for i in range(N):
    if l_2d_t[i][0]>=H:
      add=l_2d_t[i][1]
      break
  
ans=B[temp]*kaisu+add
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
f_i = stdin

H, N = map(int, f_i.readline().split())

C = [10 ** 8] * (H * 2)
C[0] = 0
for line in f_i:
    A, B = map(int, line.split())
    for i, vals in enumerate(zip(C, C[A:]), start=A):
        v1, v2 = vals
        C[i] = min(v1 + B, v2)

print(min(C[H:]))

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for x in range(n)]
min_a = min([x[0] for x in ab_array])
max_a = max([x[0] for x in ab_array])

dp = [float("inf") for x in range(max(h, max_a) + 1)]
for a, b in ab_array:
    dp[a] = b
for i in range(min_a, h + 2):
    for a, b in ab_array:
        if i + a >= h + 1:
            continue
        dp[i + a] = min(dp[i + a], dp[i] + b)
ans = dp[h]
if ans == float("inf"):
    for i in dp[h:]:
        if i != float("inf"):
            ans = min(ans, i)
            break
    amari = None
    for i in reversed(range(h + 1)):
        if dp[i] != float("inf"):
            tmp = dp[i]
            amari = h - i
            break

    if amari is not None:
        for i in range(amari, h):
            if dp[i] != float("inf"):
                tmp2 = dp[i]
                break
        ans = tmp2 + tmp

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

H, N = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a, b])

inf = 10**12
dp = [[inf for j in range(H+1)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    for j in range(1,H+1):
        if j < AB[i][0]:
            dp[i+1][j] = AB[i][1]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - AB[i][0]]+AB[i][1])

print(dp[N][H])

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]

K=[]
for i in range(N):
    K.append(AB[i][0]/AB[i][1])
MKI = K.index(max(K))

R=0
while H>0:
    H-=AB[MKI][0]
    R+=AB[MKI][1]

if H==0:
    print(R)
else:
    AB.pop(MKI)
    K.pop(MKI)
    SKI = K.index(max(K))
    while H>0:
        H-=AB[SKI][0]
        R+=AB[SKI][1]
    print(R)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
h, n = map(int, stdin.readline().rstrip().split())
magic = np.array([list(map(int, stdin.readline().rstrip().split())) for _ in range(n)])
cp = np.array([a / b for a, b in magic])
dp = [10 ** 10 for _ in range(30001)]
for a, m in magic:
    dp[a] = m

for i in range(h+1):
    if dp[i] != 10 ** 10:
        for a, m in magic:
            if i+a < 30001:
                dp[i+a] = min(dp[i+a], dp[i] + m)

print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())


import sys
sys.setrecursionlimit(999999999)

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

dic={}

def rec(magic, nokori,sum_mp):
    if nokori<=0:
        return sum_mp
    if magic >= n:
        return 10**9

    if str(magic)+"_"+str(nokori) in dic:
        return dic[str(magic)+"_"+str(nokori)]

    dmg = S[magic][0]
    mp  = S[magic][1]

    min_mp = min(
        rec(magic  ,nokori-dmg,sum_mp+mp), # use this magic, and check this magic again
        rec(magic+1,nokori-dmg,sum_mp+mp), # use this magic, and check next magic
        rec(magic+1,nokori,sum_mp       ), # don't use this magic, and check next magic
    )

    dic[str(magic)+"_"+str(nokori)] = min_mp
    return min_mp

print(rec(0,h,0))

Submission status: Wrong Answer

Solution code:
# 2020/01/26
# AtCoder Beginner Contest 153 - C

from operator import itemgetter

# Input
h, n = map(int,input().split())

ablist = list()
for i in range(n):
    l = list()
    a, b = map(int,input().split())
    efc = a / b
    l.append(a)
    l.append(b)
    l.append(efc)

    ablist.append(l)

# 効率の良い順にソート
ablist.sort(key=itemgetter(2))
ablist.reverse()

# Init
wk_h = h
usemp = 0
min_last_mp = 10 ** 9

# 最も効率的なものを使う
atcnt = wk_h // ablist[0][0]

# 最も効率的なもので2回以上かかる場合、最後の1回以外はそれを使う
if atcnt > 0:
    usemp = usemp + atcnt * ablist[0][1]
    wk_h = wk_h - atcnt * ablist[0][0]
    min_last_mp = ablist[0][1]

# 与える体力順にソート
ablist.sort(key=itemgetter(0))
ablist.reverse()

print(ablist)

i = 1
if wk_h <= 0:
    ans = usemp
else:
    while(i < n and wk_h <= ablist[i][0]):
        atcnt = wk_h // ablist[i][0]
        wk_mp = 0
        if atcnt > 0:
            if wk_h % ablist[i][0] == 0:
                wk_mp = ablist[i][1] * atcnt
            else:
                wk_mp = ablist[i][1] * (atcnt + 1)
        else:
            wk_mp = ablist[i][1]
            
        if min_last_mp > wk_mp:
            min_last_mp = wk_mp
    
        i = i + 1
    
    ans = usemp + min_last_mp

# Output
print(ans)

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
magic = []
ans = 1000000
for i in range(N):
    a,b = map(int,input().split())
    magic.append([a,b])

for i in range(N):
    for j in range(N):
        x = ((H - magic[j][0])//magic[i][0])*magic[i][1] + magic[j][1]
        if (H - magic[j][0])% magic[i][0] != 0:
            x += magic[i][1]
        ans = min(ans,x)
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = input().split()
H = int(H)
N = int(N)
a = []
b = []
con = 1
while con <= N:
    A, B = map(int, input().split())
    a.append(A)
    b.append(B)
    con += 1
print(sum(b))

Submission status: Wrong Answer

Solution code:
i=list(map(int,input().split()))
h=i[0]
mp=0
mls=[[0,0]]*i[1]
pls=[[0,0]]*i[1]
for k in range(i[1]):
  mls[k]=list(map(int,input().split()))
  pls[k]=[float(mls[k][0])/mls[k][1],k]
pls.sort(reverse=True)
fp=mls[pls[0][1]][0]
fm=mls[pls[0][1]][1]
kaz=h//fp
h=h-(fp*(kaz))
mp=fm*kaz
if h>0:
  for v in range(i[1]):
    sp=mls[v][0]
    sm=mls[v][1]
    if sp>=h and sm<fm:
      fm=sm
  mp+=fm
print(mp)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    H,N = map(int,input().split())
    # AB = [list(map(int,input().split())) for _ in range(N)]
    A = []
    B = []
    for i in range(N):
        temp = list(map(int,input().split()))
        A.append(temp[0])
        B.append(temp[1])

    A = np.array(A)
    B = np.array(B)

    C = A / B
    best = np.argmax(C)

    bestA = A[best]
    bestB = B[best]

    D = [0 for _ in range(N*2)]

    for i in range(N):
        now = H
        time = -(-bestA//A[i])
        now -= A[i] * time
        D[i] += B[i] * time
        if now > 0:
            time = - (-now // bestA)
            D[i] += bestB * time

    for i in range(N):
        now = H
        time = bestA//A[i]
        now -= A[i] * time
        D[N+i] += B[i] * time
        if now > 0:
            time = - (-now // bestA)
            D[N+i] += bestB * time

    res = min(D)
    print(res)





main()

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
a = []
b = []
for i in range(n):
  a_dash,b_dash = map(int,input().split())
  a.append(a_dash)
  b.append(b_dash)

#dp[i][j]=i番目までで体力jのモンスターに勝てる魔力の合計の最小値
dp = [[10**7 for _ in range(h+1)] for _ in range(n+1)]

for i in range(n):
  for j in range(h+1):
    if j < a[i]:
      #dp[i+1][j] = min(dp[i][j],b[i])
      dp[i+1][j] = b[i]
    else:
      dp[i+1][j] = min(dp[i][j],dp[i+1][j-a[i]]+b[i])

print(dp[n][h-1])

Submission status: Wrong Answer

Solution code:
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=0
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(h):
        for j in l:
            a,b=j[0],j[1]
            x=d[i]+b
            if i==0 or (d[i]!=0 and d[i+a]==0):
                d[i+a]=x
            elif d[i]!=0 and d[i+a]!=0:
                d[i+a]=min(d[i+a],x)
    for i in range(h,20005):
        if ans==0:
            ans=d[i]
        elif d[i]!=0:
            ans=min(ans,d[i])
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
H,N=map(int, input().split())
A=[0]*N
B=[0]*N
for i in range(N):
    A[i],B[i]=map(int, input().split())
kouritu=[0]*N
kouritu_max=0
kouritu_i=0
B_kouritu=10000
todomeMP=10000
for i in range(N):
    kouritu[i]=float(A[i]) / float(B[i])
    if kouritu_max<=kouritu[i] and B_kouritu>=B[i]:
        kouritu_i=i
        kouritu_max=kouritu[i]
        B_kouritu=B[i]
if H%kouritu_max==0:
    print(H/kouritu_max)
else:
    hantei=0
    count=0
    while hantei==0:
        if H>A[kouritu_i]:
            H=H-A[kouritu_i]
            count+=B[kouritu_i]
        else:
            for j in range(N):
                if H<=A[j] and todomeMP>=B[j]:
                    todomeMP=B[j]
            hantei=1
        for j in range(N):
            if A[j]<=H:
                for i in range(100):
                    if B[j]*i>=H and B[j]*i<=todomeMP:
                        todomeMP=B[j]*i
                        break
    print(int(count+todomeMP))

Submission status: Wrong Answer

Solution code:
import numpy as np
H, N = [int(s) for s in input().split()] 
AB = [[int(s) for s in input().split()] for i in range(N)]
ABe = np.array([[AB[i][0], AB[i][1], AB[i][0]/AB[i][1]] for i in range(N)])
ABe = ABe[ABe[:,2].argsort()[::-1], :]
consumption = 0
while H > 0:
  choice = 0
  for i in range(N):
    if H > ABe[i, 0]:
      choice = i
      break
  for i in range(N):
    if H <= ABe[i, 0] and ABe[i, 1] < ABe[choice, 1]:
      choice = i
  H -= int(ABe[choice, 0])
  consumption += int(ABe[choice, 1])
print(consumption)

Submission status: Wrong Answer

Solution code:
import math
def A():
    temp = [int(i) for i in input().split()]
    print(int(math.ceil(temp[0]/temp[1])))

def B():
    temp = [int(i) for i in input().split()]
    H = temp[0]
    N = temp[1]
    A = [int(i) for i in input().split()]
    if H <= sum(A):
        print('Yes')
    else:
        print('No')

def C():
    temp = [int(i) for i in input().split()]
    N = temp[0]
    K = temp[1]
    H = [int(i) for i in input().split()]
    if N <= K:
        print(0)
        return
    H.sort(reverse=True)
    print(sum(H[K:]))

def D():
    H = int(input())
    factor = 0
    ans = 0
    while True:
        ans += 2**factor
        if H == 1:
            break
        H = math.floor(H/2)
        factor += 1
    print(ans)

def E():
    temp = [int(i) for i in input().split()]
    H = temp[0]
    N = temp[1]
    magic = []
    for i in range(N):
        magic.append(tuple([int(i) for i in input().split()]))
    magic.sort(key = lambda x: x[1])
    attack = [k for k, v in magic]
    cost = [v for k,v in magic]

    min_cost = [[0 for i in range(H+1+min(attack))] for j in range(N+1)] 
    
    for i in range(H+1+min(attack)): 
        min_cost[0][i] = float('inf')
  
    for i in range(1, N+1): 
        min_cost[i][0] = 0

    for i in range(1, N+1): 
        for j in range(1, H+1+min(attack)): 

            if (attack[i-1] > j): 
                min_cost[i][j] = min_cost[i-1][j] 
  
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-attack[i-1]] + cost[i-1]) 
    
    #print(min_cost)
    if(min_cost[N][H] == float('inf')): 
        i = 1
        while H+i < H+1+min(attack):
            if min_cost[N][H+i] < float('inf'):
                print(min_cost[N][H+i])
                return
    else: 
        print(min_cost[N][H])

E()

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
maho=[]
ans=[]
for i in range(n):
    a,b=map(int,input().split())
    c=a/b
    maho.append([c,a,b])
maho2=sorted(maho,reverse=True)
if h%maho2[0][1]==0: #一番コスパいいやつだけ使うと、ぴったり倒せる
    print((h//maho2[0][1])*maho2[0][2])
else:
    print(0)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# ans=1
# for i in range(n):
#     ans+=a[i][0]
M=10**12
dp=[[M for i in range(3*h+2)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(3*h+2):
        if j<a[i][0]:
            dp[i+1][j]=dp[i][j]
        elif dp[i+1][j-a[i][0]]<M and dp[i][j]<M:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i][0]]+a[i][1])
        elif dp[i+1][j-a[i][0]]<M:
            dp[i+1][j]=dp[i+1][j-a[i][0]]+a[i][1]
        elif dp[i][j]<M:
            dp[i+1][j]=dp[i][j]
for i in range(n+1):
    print(dp[i])
for i in range(h,3*h+2):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

Submission status: Wrong Answer

Solution code:
from operator import attrgetter

h, n = map(int, input().split())
arr = []

class Magic:
    def __init__(self, a, b, ab):
        self.a = a
        self.b = b
        self.ab = ab

for _ in range(n):
    a, b = map(int, input().split())
    arr.append(Magic(a, b, a/b))


arr.sort(key=attrgetter('b'))
arr.sort(key=attrgetter('ab'), reverse=True)

#for _ in arr:
#    print(_.a, _.b, _.ab)

ans = 0
hp = h
hp_remain = 0

while hp > 0:
    length = len(arr)
    l = 0
    for i in arr:
        if hp >= i.a:
            ans += i.b
            hp -= i.a
            print(hp, ans)
            break
        l += 1
        if l == length-2:
            hp_remain = hp
            hp = 0

#print(hp_remain)
min_magic = 10000

if hp_remain > 0:
    for i in arr:
        if hp_remain <= i.a:
            if min_magic > i.b:
                min_magic = i.b

print(ans + min_magic)

Submission status: Wrong Answer

Solution code:
h,n = map(int, input().split())
l = []
for _ in range(n):
    a, b = map(int, input().split())
    l.append([a,b])
d = sorted(l, key=lambda x: x[0]/x[1], reverse=True)

res = 0 
cnt = len(d)

while h > 0:
    tt = 10e+10
    ss = 10e+10
    for i in range(cnt):
        if ((h - d[i][0]) >= 0) and (tt > d[i][1]):
            res += d[i][1]
            h -= d[i][0]
            break
        else:
            if tt > d[i][0]:
                tt = d[i][0]
                ss = d[i][1]
                if i == (cnt-1):
                    h -= tt
                    res += ss
print(res)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
lis = []
lis2 = []
wari = 0
dam = 0
mp = 0
use = 0
from math import ceil
for l in range(n):
    a, b = map(int, input().split())
    lis.append([a, b])
    lis2.append(a / b)
    if wari < a / b :
        wari = a / b
        dam = a
        mp = b
lis2[lis2.index(wari)] = 0
use = (h // dam) * mp
h = h % dam

if h != 0:
    if mp > lis[lis2.index(max(lis2))][1]:
        dam = lis[lis2.index(max(lis2))][0]
        mp = lis[lis2.index(max(lis2))][1]
        use = use + (h // dam) * mp
        h = h % dam
        lis2[lis2.index(max(lis2))] = 0
        if h != 0:
            if mp > lis[lis2.index(max(lis2))][1]:
                dam = lis[lis2.index(max(lis2))][0]
                mp = lis[lis2.index(max(lis2))][1]
                use = use + ceil(h / dam) * mp
                h = h % dam
                lis2[lis2.index(max(lis2))] = 0
            else:
                use = use + mp
    else:
        use = use + mp
print(use)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
def ans(h,a):
    if h%a==0:
        return h//a 
    else:
        return h//a+1
n,H=map(int,input().split())
nn=n
a,b=[],[]
s=0
J=[]
JJ=[]
for i in range(H):
    aa,bb=map(int,input().split())
    J.append([aa,bb])
    JJ.append([bb,aa])
J.sort()
a=[x[0] for x in J]
b=[x[1] for x in J]
#a,b=[],[]
while n>0:
    f=bisect_left(a,n)
    s+=b[max(0,f-1)]
    n=n-a[max(0,f-1)]
ff=[s]
#print(a)
n=nn
for i in range(len(a)):
    ss=b[i]*ans(n,a[i])
    ff.append(ss)
#print(ff)

kk=min(ff)
s=0
JJ.sort()
a=[x[1] for x in JJ]
b=[x[0] for x in JJ]
while n>0:
    f=bisect_left(a,n)
    s+=b[max(0,f-1)]
    n=n-a[max(0,f-1)]
print(min(kk,s))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
import math 
H, N = map(int, input().split())
AB = []

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

AB.sort(key=lambda x: -(x[0] / x[1]))

ans = float("inf")
for (attack, mp) in AB:
  hp = H
  cnt = hp // attack
  hp -= cnt * attack
  tmp1 = mp * cnt

  if hp == 0:
    ans = min(ans, tmp1)
    continue

  tmp2 = float("inf")
  for (a, b) in AB:
    # 何回攻撃しないといけないか算出
    c = 1 if hp <= a else math.ceil(hp / a)
    tmp2 = min(tmp2, b * c)

  print(tmp1, tmp2, 139815 % attack)
  ans = min(ans, tmp1 + tmp2)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, N = map(int, input().split(' '))
    max_attack = 0
    magic_list = list()
    best_dps = 0
    best_dps_index = 0
    for n in range(N):
        magic_list.append(list(map(int, input().split(' '))))
        if max_attack < magic_list[n][0]: max_attack = magic_list[n][0]
        if best_dps < magic_list[n][0] / magic_list[n][1]:
            best_dps = magic_list[n][0] / magic_list[n][1]
            best_dps_index = n
    best_attack, best_attack_mp = magic_list[best_dps_index][0], magic_list[best_dps_index][1]
    attack_cnt, remaining_hp = divmod(H, best_attack)
    mp_cnt = attack_cnt * best_attack_mp
    magic_list.sort()
    if remaining_hp > 0:
        for magic in magic_list:
            hp = remaining_hp
            magic_cnt = 1
            if magic[0] > hp and best_attack_mp < magic[1]:
                magic_cnt = magic[0] // best_attack
                if magic_cnt == 0: magic_cnt = 1
                hp += magic_cnt * best_attack
            mp = (0 - -hp // magic[0]) * magic[1]
            if best_attack_mp * magic_cnt > mp:
                best_attack_mp = mp
                if magic_cnt > 1:
                    mp_cnt -= magic_cnt
        mp_cnt += best_attack_mp
    print(mp_cnt)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
h,n=map(int,input().split())
a=np.array([0]*n)
b=np.array([0]*n)
t=np.array([0.0]*n)
H = h
c = 0
min_b = 10000000
for i in range(n):
	a[i],b[i]=map(int,input().split())
	t[i]=a[i]/b[i]
x = np.sort(t)[-1::-1]
d = a[np.argsort(t)[-1]]
#print(t,np.argsort(t)[-1])
max_a=max(a)
while H > max(a):
	c += 1
	H -= d
	#print(a[np.argsort(t)[-1]],H,c)
H_nokori = h - d*(c-1)
k = 0
#print(c-1)
for i in range(n):
	if H_nokori % a[i] == 0:
		k = H_nokori // a[i]
		if b[i] * k < min_b:
			min_b = b[i] * k 
	else:
		k = H_nokori //a[i] +1
		if b[i] * k < min_b:
			min_b = b[i] * k 
#print(min_b)
print(b[np.argsort(t)[-1]]*(c-1) + min_b)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
import math
import itertools
def main():
    H, N = map(int, input().split())
    magic = []

    for _ in range(N):
        A, B = map(int, input().split())
        C = A/B
        magic.append((A, B, C))
    magic = sorted(magic, key=lambda x: x[0], reverse=True)
    magic = sorted(magic, key=lambda x: x[1], reverse=False)
    magic = sorted(magic, key=lambda x: x[2], reverse=True)
    #print(magic)

    ans = 0
    while True:
        if H <= 0:
            break
        kouritu = magic[0]
        if kouritu[2] > H:
            ans += kouritu[1]
            H -= kouritu[0]
            magic.pop(0)

        else:
            ans += kouritu[1]
            H -= kouritu[0]
            if kouritu[2] > H:
                magic.pop(0)

    print(ans)

    return 0
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

H,N = map(int, input().split())
D=list()
for i in range(N):
    a,b = map(int, input().split())
    D.append((a, b, a/b))
ans = 0
M = list(sorted(D, key=lambda tup: tup[2], reverse=True))

ans = (H // M[0][0]) * M[0][1]
H = H % M[0][0]
if H == 0:
    print(ans)
    sys.exit()

dp = [[H]]

mi = float("inf")
for d in M:
    mp = (H // d[0]) * d[1]
    if H % d[0] != 0:
        mp += d[1]
    if mi > mp:
        mi = mp
ans += mi

print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
a = []
b = []
# effectiveness
c = []
steps = []
sum_mp = 0
for i in range(N):
  _a, _b = map(int, input().split())
  a.append(_a)
  b.append(_b)
  c.append(_a / _b)
c_max = max(c)
index = c.index(c_max)
best_a = a[index]
best_b = b[index]
while H > 0:
  dummy = []
  for i in range(N):
    if H - a[i] <= 0:
      dummy.append(a[i])
  if len(dummy) != 0:
    min_mp = min(dummy)
    sum_mp += min_mp
    break
  H -= best_a
  sum_mp += best_b
print(sum_mp)