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:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas



H, N = mulinputs()
ABpairs = []
while True:
    try:
        ABpairs.append(list(map(int, input().split())))
    except EOFError:
        break

# # テスト出力
# print(H, N, ABpairs)

min_magic = (-1,-1)
min_tmp = 1010001000
for t in ABpairs:
    if t[1] < min_tmp:
        min_tmp = t[1]
        min_magic = t

hi_performed_magic = -1
max_tmp = 0
_abp = [(ab[0]/ab[1],  ab[0], ab[1]) for ab in ABpairs]
abpd = dict()
for t in _abp:
    if t[0] not in abpd.keys():
        abpd[t[0]] = (t[1],t[2])
        continue
    if abpd[t[0]][1] > t[2]:
        abpd[t[0]] = (t[1],t[2])
        continue

k = list(abpd.keys())
k.sort(reverse=True)
cost = 0
idx=0
l = len(k)
while H > 0:
    if H < abpd[k[idx]][0] and idx < l-1 and abpd[k[idx]][1] > abpd[k[idx]][1]:
        idx += 1
        continue
    H -= abpd[k[idx]][0]
    cost += abpd[k[idx]][1]
print(cost)
#print(abp)
# for t in abp:
#     if t[0] > max_tmp:
#         max_tmp = t[0]
#         hi_performed_magic = (t[1], t[2])
# 
# cost = 0
# while H >= hi_performed_magic[0]:
#     H -= hi_performed_magic[0]
#     cost += hi_performed_magic[1]
# 
# while H < hi_performed_magic[0] and H > 0:
#     H -= min_magic[0]
#     cost += min_magic[1]

# idx = 0
# while H > 0:
#     if H < abp[idx]
# 
# print(cost)

# min_cost = 1010001000
# 
# def greedy(h, cost):
#     if h <= 0:
#         return cost
#     for i in range(N):
#         a, b = ABpairs[i]
#         cost += greedy(h-1,b)
#     return -1
# 
# # 出力
# print(greedy(H, 0))

Submission status: Wrong Answer

Solution code:
def main():
    H, N = map(int, input().split())
    cnt = 0
    AB = [list(map(int, input().split())) for i in range(N)]
    ABrate = [i[1]/i[0] for i in AB]
    min_index = ABrate.index(min(ABrate))
    min_rate = AB[min_index]
    past = [10000,10000]
    C = [i[0] for i in AB]
    maxAB = max(C)
    while H > maxAB:
        H -= min_rate[0]
        cnt += min_rate[1]

    while H > 0:
        for i in range(N):
            if i == ABrate.index(min(ABrate)):
                pass
            elif AB[i][0] >= H and ABrate[i] < past[1]:
                past = [i,ABrate[i]]
        if cnt+AB[i][0] >= cnt+min_rate[1]:
            H -= min_rate[0]
            cnt += min_rate[1]
        elif cnt+AB[i][0] < cnt+min_rate[1]:
            H -= AB[i][0]
            cnt += AB[i][1]

    print(cnt)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[]
for _ in range(n):
  a=list(map(int,input().split()))
  l.append(a)
ans=0
while h>0:
  k=[]
  for i in l:
    s=i[0]
    t=i[1]
    if h>=s:
      k.append(s/t)
    else:
      k.append(h/t)
  b=k.index(max(k))
  c=l[b]
  ans+=c[1]
  h=h-c[0]
  if ans>100000:
    print(ans,k,c)
print(ans)

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(max(h+10010,2*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(max(h+10010,2*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,max(h+10010,2*h+2)):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
L=[]
for i in range(n):
       a,b=map(int,input().split())
       c=a/b
       L.append((a,b,c))
L.sort(key=lambda x:x[2],reverse=True)

ans=0
i=0
while h>0:
       if h>=L[i][0]:
              h=h-L[i][0]
              ans+=L[i][1]
              if h<=0:
                     print(ans)
                     exit()
       else:
              i+=1
              if i==n:
                  L.sort(key=lambda x:x[1])
                  ans+=L[0][1]
                  print(ans)
                  exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N=map(int,input().split())
A_list,B_list,R_list=[],[],[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)
    R_list.append(A/B)
A_list=np.array(A_list);B_list=np.array(B_list);R_list=np.array(R_list)
idx=np.argsort(A_list)
A_init=A_list[idx];B_init=B_list[idx];R_init=R_list[idx]
los=0
H_res=H
for idx,R in enumerate(R_init):
    los+=(H_res//A_init[idx])*B_init[idx]
    H_res=H_res%A_init[idx]
if H_res==0:
    print(los)
else:
    print(los+min(B_init))

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
rAB = [(a/b, a, b) for a, b in AB]
rAB.sort(reverse=True)

# print(rAB, rAB[0])

ans = 10 ** 12
for i in rAB:

  _, x, y = i

  for a, b in AB:
    sm = h
    cnt = (sm - a - 1) // x + 1
    cost = b + cnt * y
    ans = min(ans, cost)
  
print(ans)

Submission status: Wrong Answer

Solution code:
import math

H, N = [int(num) for num in input().split(' ')]

INFO = []

for i in range(N):
	Ai,Bi = [int(num) for num in input().split(' ')]
	INFO.append((Ai, Bi, float(Ai)/float(Bi)))
    

INFO = sorted(INFO, key=lambda x:x[2], reverse=True)

magic=0
while H>0:
	if INFO[0][0]>H:
		for i, (A, B, E) in enumerate(INFO):
			new = (H, B, float(Ai)/float(Bi))
			INFO[i] = new
		INFO = sorted(INFO, key=lambda x:x[2], reverse=True) 
	
	A, B, E = INFO[0]
	H-=A
	magic+=B

print(magic)

Submission status: Wrong Answer

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

c = []
for i in range(n):
    c.append(a[i]/b[i])

d = c.index(max(c))
e = b.index(min(b))
ans = 0
while h-a[d]>=0:
        h = h -a[d]
        ans += b[d]
while h -a[e]>=0:
        h = h -a[e]
        ans += b[e]
print(ans + b[e])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ab_list = [[int(j) for j in input().split()] for i in range(n)]

temp = [a[0]/a[1] for a in ab_list]
max_index = temp.index(max(temp))

first_num = h//ab_list[max_index][0]
first_cost = first_num*ab_list[max_index][1]
first_damage = ab_list[max_index][0]*first_num

h -= first_damage

if h==0:
    print(first_cost)
else:
    second_cost_list = []
    for ab in ab_list:  
        if ab[0] >= h:
            second_cost_list.append(ab[1])

    print(first_cost+min(second_cost_list))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
a = [0] * N
b = [0] * N
x = [0] * N
for i in range(N):
    a[i], b[i]  = map(int, input().split())
    x[i] = a[i]/b[i]

xMaxIndex = x.index(max(x))
Last = H%a[xMaxIndex]
MP_NOW = b[xMaxIndex] * (H//a[xMaxIndex])

for n in range(len(a)):
  if(a[n] < Last):
    b[n] = b[n] * (-(-Last//a[n]))

BMinIndex = b.index(min(b))
count = -(-Last//a[BMinIndex])
print(MP_NOW + (b[BMinIndex] * count))

while H > 0:
    if(a[n] < H):
      b[n] = b[n] * (-(-Last//a[n]))
      BMinIndex = b.index(min(b))
      count = -(-Last//a[BMinIndex])
    H = H%a[BMinIndex]
    MP_NOW += b[BMinIndex] * (H//a[BMinIndex])

print(MP_NOW)

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
Max2=0
add=0
temp=0
temp2=0
for i in range(N):
  A[i],B[i]=map(int,input().split())
  C[i]=A[i]/B[i]
  if Max<C[i]:
    Max2=Max
    temp2=temp
    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
kaisu2=H//A[temp2]
H=H-A[temp2]*kaisu2
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+B[temp2]*kaisu2+add
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
ans=0
h,n=list(map(int,input().split()))
magic=[list(map(int,input().split())) for _ in range(n)]
cost=[min(magic[i][0],h)/magic[i][1]for i in range(n)]
tmp=100000000000000000
while(n>0):
  index=np.argmax(np.array(cost))
  ans+=(h//magic[index][0])*magic[index][1]
  h=h%magic[index][0]
  
  if h==0:
    tmp=min(ans,tmp)
  else:
    for i in range(len(magic)):
      hp=h-magic[i][0]
      _ans=ans+magic[i][1]
      _ans-=-hp//magic[index][0]*magic[index][1]
      tmp=min(_ans,tmp)
    tmp=min(ans+magic[index][1],tmp)
  n-=1
  magic.pop(index)
  cost.pop(index)
print(tmp)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
h, n = map(int, input().split())
a_list = []
dict_a_b1 = {}
dict_a_b2 = {}
for i in range(0, n):
    a, b = map(int, input().split())
    a_list.append(a)
    dict_a_b1[a] = b
    dict_a_b2[a] = a/b
a_list.sort()
flag = 0
min_score = 10**6
for a, v in sorted(dict_a_b2.items(), key=lambda x: -x[1]):
    b = dict_a_b1[a]
    if a < h:
        flag += 1
        if h % a == 0:
            m = h // a
            min_score = min(min_score, m * b)
            break
        else:
            m = h // a
            min_score = min(min_score, (m + 1) * b)
            hh = h - m * a
            for a1 in a_list:
                if a1 >= a:
                    break
                mm = hh // a1
                min_score = min(min_score, (mm + 1) * dict_a_b1[a1] + m * b)
                
    else:
        min_score = min(min_score, b)
    if flag == 3:
        break

print(min_score)

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
a,b = [],[]
ans = 0

for _ in range(n):
  at,bt = map(int,input().split())
  a.append(at)
  b.append(bt)

ab = [a[i]/b[i] for i in range(n)]
bestindex = [value for i, value in enumerate(ab)]
thebest = ab.index(max(bestindex))

#print(thebest)

#残体力
lasth = h%a[thebest]
#使用魔力
ans = b[thebest]*h//a[thebest]
#print(lasth)
#print(ans)

lastindex = []
if lasth != 0:
  for i in range(n):
    if lasth <= a[i] and b[i] <= b[thebest]:
      lastindex.append(b[i])
  ans += min(lastindex)

print(ans)



'''
最高効率で０になる直前まで削る
残ったHPを削り取る最高効率を探す。






print('{} {}'.format(h,n))print(a)
print(b)
'''

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

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

    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:
import math
inf = 10 ** 12

def main():
    h,n = map(int,input().split())
    magic_lst = []
    mp_counter = 0
    for i in range(n):
        magic_lst.append(list(map(int,input().split())))

    #MP効率の良い順に魔法を並び替える。
    magic_lst.sort(key=lambda x:x[0] / x[1])
    magic_lst.reverse()
    todome = False
    for magic in magic_lst:
        if magic[0] >= h and not todome:
            mn = magic[1]
            todome = True
        elif magic[0] <= h and not todome:
            mp_counter += magic[1] * (h // magic[0])
            h = h % magic[0]
            todome = True
            mn = magic[1]
        elif todome:
            if math.ceil(h/magic[0]) * magic[0] < mn:
                mp_counter += magic[1] * (h // magic[0])
                h = h % magic[0]
                if h == 0:
                    break
                mn = magic[1]

    print(mp_counter + mn)









if __name__ == '__main__':
    main()

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**12] * (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 math
import numpy as np
H, N = map(int,input().split())

A_list = []
B_list = []
for _ in range(N):
  A, B = map(int,input().split())
  A_list.append(A)
  B_list.append(B)
 
A = np.array(A_list)
B = np.array(B_list)

magic_used = 0

def choose_attack(H):
    A_star = np.minimum(A, H)
    performace = np.divide(A_star,B)
    ind = np.argmax(performace)
    return ind

while H >= 0:
    ind = choose_attack(H)
    magic_used += B[ind]
    H = H - A[ind]

print(magic_used)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
A=[]
B=[]
C=[]
x=0
y=0
ans=0
mp=0
u=0
v=0
r=0
d=0
e=0
mon=H
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
for i in range(N):
  if A[i]//B[i]>x:
    x=A[i]//B[i]
    y=i

#print(y,A[y],B[y])

while H>A[y]:
  H=H-A[y]
  ans=ans+1
  mp=ans*B[y]
#print(ans,A[y],H,mp)

u=B[y]
for i in range(N):
  if H%A[i]!=0:
    if (H//A[i]+1)*B[i]<u:
      u=(H//A[i]+1)*B[i]
      v=i
  else:
    if (H//A[i])*B[i]<u:
      u=(H//A[i]+1)*B[i]
      v=i
#print(mp+u)

p1=mon-(ans-1)*A[y]
d=mp+u
for i in range(N):
  if p1%A[i]!=0:
    if (p1//A[i]+1)*B[i]<d:
      d=(p1//A[i]+1)*B[i]
      e=i
  else:
    if (p1//A[i])*B[i]<d:
      d=(p1//A[i])*B[i]
      e=i
#print(d)
print((ans-1)*B[y]+d)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)
while H>0 :
    while H>=ar[count][0]:
        H-=ar[count][0]
        ans+=ar[count][1]

    if H<ar[count][0] and count!=N-1:
        count+=1
    if count==N-1:
        H-=ar[count][0]
        ans+=ar[count][1]
print(ans)

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[pls[v][1]][0]
    sm=mls[pls[v][1]][1]
    if sp>=h and sm<fm:
      fm=sm
    elif sp<h:
      h=h-sp
      mp+=sm
  mp+=fm
print(mp)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = []
B = []
for i in range(N):
  ai, bi = map(int, input().split())
  A.append(ai)
  B.append(bi)

import math

magic_cost = 0
while(H > 0):
  # その体力に対して、もっとも効率の良い魔法を選ぶ
  max_e = 0
  best_a, best_b = 0, 0
  for a, b in zip(A, B):
    if a > H: # 残り体力よりも攻撃力が高い時
      e = H / b
    else:
      e = a / b


    if max_e < e:
      best_a = a
      best_b = b
      max_e = e


  if best_a >= H: # その一撃が終わりの時
    magic_cost += best_b
    H = 0
  else:  
    magic_cost += math.floor(H / best_a) * best_b
    H = H - math.floor(H / best_a) * best_a


print(magic_cost)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

H, N = map(int, input().split())
magic = []

max_damage = 0

for _ in range(N):
    A, B = map(int, input().split())
    max_damage = max(A, max_damage)
    magic.append([A / B, A ,B])

magic.sort(key=itemgetter(1), reverse=True)
magic.sort(key=itemgetter(0), reverse=True)

ans = 0


def find_min_mp(rest, index, last):
    if rest == 0:
        return 0
    for choice in magic[index:]:
        if rest < choice[1]:
            continue
        else:
            use_count = rest // choice[1]
            next_rest = rest - use_count * choice[1]
            return min(last, use_count * choice[2] + find_min_mp(next_rest, index + 1, choice[2]))

    min_mp = last
    for choice in magic[index:]:
        min_mp = min(min_mp,choice[2])

    return min_mp


ans = find_min_mp(H, 0, 10 ** 9)

print(ans)

Submission status: Wrong Answer

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


amount = H + 1
dp = [float('inf')] * (amount + 1)
dp[0] = 0

for amt in range(1, amount + 1):
    t = [dp[amt - coin] + b if amt - coin >= 0 else float('inf') for coin, b in magic]
    dp[amt] = min(t)

if dp[H] == float('inf'):
    print(dp[-1])
else:
    print(dp[H])

Submission status: Wrong Answer

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*10**4 for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][1]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import ceil
H, N = map(int, input().split())
l = []
L = []
for i in range(N):
    a, b = map(int, input().split())
    L.append([a, b, a/b])
# exit()
L.sort(key=lambda x: x[2], reverse=True)
# print(*L)
# exit()
cnt = 0
ans = float("inf")
# while H >= L[0][0]:
while H > 0:
    # H -= L[0][0]
    # cnt += L[0][1]
    l = []
    for i in range(N):
        l.append(ceil(H / L[i][0]) * L[i][1])
    tmp = min(l)
    idx = l.index(tmp)
    ans = min(ans, cnt+tmp)
    H -= L[idx][0]
    cnt += L[idx][1]
# L.sort(key=lambda x: x[1])
# print(*l)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math

h,n = list(map(int,input().split()))
a=[0]*n
b=[0]*n
c=[0]*n

minn=99999

for i in range(n):
    a[i],b[i]=list(map(int,input().split()))
    c[i]=a[i]/b[i]
    if b[i]<minn:
      minn=b[i]

mgc=0

c,a,b=zip(*sorted(zip(c,a,b),reverse=True))

kouho=[]

for i in range(n):
    while(h>=a[i]):
        h-=a[i]
        mgc+=b[i]
        
    if h==0:
        kouho.append(mgc)
    else:
      	for k in range(i):
            kouho.append(mgc+b[k])
          
print(min(kouho))

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(b[i])
  if len(dummy) >= 1:
    min_mp = min(dummy)
    sum_mp += min_mp
    break
  H -= best_a
  sum_mp += best_b
print(sum_mp)

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

MAGIC = sorted(MAGIC, key=lambda x: x[0])
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:


def main():
    from operator import itemgetter
    import math
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    ans = 0
    cp = [AB[i][0]/AB[i][1] for i in range(N)]
    AB = sorted([[AB[i][0],AB[i][1],cp[i]] for i in range(N)],key=itemgetter(1))
    AB = sorted(AB,key=itemgetter(2),reverse=True)
    if AB[0][0] >= H:
        AB = sorted(AB,key=itemgetter(1))
        for i in range(N):
            if H <= AB[i][0]:
                print(AB[i][1])
    else:
        for i in range(N):
            ans += (math.floor(H/AB[i][0]))*AB[i][1]
            H -= (math.floor(H/AB[i][0]))*AB[i][0]
            if H <= 0:
                break
        if H <= 0:
            print(ans)
        else:
            AB = sorted(AB,key=itemgetter(1))
            for i in range(N):
                if H <= AB[i][0]:
                    ans += AB[i][1]
                    break
            print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(100000)

def MP(i, left, N, M):
    if i == N - 1:
        iat = left // M[i][1]
        if left % M[i][1] > 0: iat += 1
        return iat * M[i][2]
    else:
        iat = left // M[i][1]
        ileft = left - iat * M[i][1]
        iMP = iat * M[i][2]
        addMP = M[i][2]
        if ileft == 0: return iMP
        else:
            nextMP = MP(i+1, ileft, N, M)
            return iMP + min(addMP, nextMP)

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [None] * N
    for i in range(N):
        a, b = map(int, input().split())
        M[i] = (a/b, a, b)
    M.sort(reverse = True)
    #print(M)
    ans = MP(0, H, N, M)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

s = input().split()
H = int(s[0])
N = int(s[1])

m = np.array([list(map(int, input().split())) for i in range(N)])
A = m[:, 0]
B = m[:, 1]

def func(H, m):
    A = m[:, 0]
    B = m[:, 1]

    if H < A[i]:
        i = np.argmin((H // A) * B)
        return (H // A[i]) * B[i]
    else:
        i = np.argmax(A / B)
        H_next = H - (H // A[i]) * B[i] 
        return (H // A[i]) * B[i] + func(H_next)
        
        func(H_next, )
        j = np.argmin(B)
        print((H // A[i])*B[i] + B[j])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = []
B = []
h = [10 ** 18] * (H + 1)

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

for i in range(N):
    hi = H
    M = B[i]
    while hi - A[i] >= 0:
        hi = hi - A[i]
        h[hi] = min(h[hi], M)
        M += B[i]
        # print(a, b, h)
    h[0] = min(h[0], h[hi] + B[i])
    # print(i, hi, hi - a, h[hi] + b)
# print(h)
print(h[0])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = []
B = []
C = []

for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
    C.append(a/b)

# max
max_value = max(C)
max_index = C.index(max_value)


if H%A[max_index] == 0:
    ans = (H//A[max_index])*B[max_index]
    
else:
    ans = (H//A[max_index])*B[max_index]    
    nokori = H%A[max_index]
    min_B = 10**4
    
    for i in range(N):
        if nokori <= A[i]:
            if min_B > B[i]:
                min_B = B[i]
        else:
            nn = nokori//A[i] + 1
            if min_B > B[i]*nn:
                min_B = B[i]*nn
    
    ans += min_B
    
        
print(ans)

Submission status: Wrong Answer

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

for line in P:
    line.append(line[0] / line[1])
    
P.sort(key=lambda x: x[2], reverse=True)

count = 0
prevLine = P[0]
prevCount = 99999
for line in P:
    #print(line, count, N)
    while N > 0 :
        N -= line[0]
        count += line[1]
    if (N < 0):
        N += line[0]
        count -= line[1]
    if (prevCount + prevLine[1] > count + line[1]):
        prevLine = line
        prevCount = count
#print(prevCount, prevLine, count )
if (N > 0):
    count += prevLine[1]

print(count)

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:
H, N = map(int, input().split())
A = []
B = []
for i in range(N):
  ai, bi = map(int, input().split())
  A.append(ai)
  B.append(bi)

import math

magic_cost = 0
while(H > 0):
  # その体力に対して、もっとも効率の良い魔法を選ぶ
  max_e = 0
  best_a, best_b = 0, 0
  for a, b in zip(A, B):
    if a > H: # 残り体力よりも攻撃力が高い時
      e = H / b
    else:
      e = a / b

    print(a, b, e)

    if max_e < e:
      best_a = a
      best_b = b
      max_e = e

  if best_a >= H: # その一撃が終わりの時
    magic_cost += best_b
    H = 0
  else:  
    magic_cost += math.floor(H / best_a) * best_b
    H = H - math.floor(H / best_a) * best_a

print(magic_cost)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N=map(int,input().split())
X=np.array([0,0])
Q=np.array([X for i in range(N)])
maxA=0
maxC=0
for i in range(N):
	A,B=map(int,input().split())
	Q[i]=np.array([A,B])

Qmax=np.max(Q,axis=0)
Bmax=min(Qmax[1],H)
print(Bmax)
	
P=np.array([1+H*N*100001 for i in range(H+1)])
P[0]=0
for k in range(1,Bmax+1):
	for i in range(N):
		P[k]=min(P[max(0,k-Q[i][0])]+Q[i][1],P[k])
for k in range(Bmax+1,H+1):
	for i in range(N):
		P[k]=min(P[k-Q[i][0]]+Q[i][1],P[k])
print(P[H])

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:
    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:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)

while H>=ar[count][0]:
    H-=ar[count][0]
    ans+=ar[count][1]
    """if len(ar)==1:
        while H>0:
            H-ar[count][0]
            count+=1"""
    if H<ar[count][0] and count!=N-1:
            count+=1
    if count==N-1:
        ans+=ar[count][1]
print(ans)