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:
def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for i in range(1, H+1):
    for n in range(N):
      a, b = ab_li[n]
      if i == a:
        dp[i] = min(dp[i], b)
      if (i < a) or (dp[i-a] == float('inf')):
        continue
      dp[i] = min(dp[i], dp[i-a]+b)
      #print(i,n)
      #print(dp)
  if dp[-1] == float('inf'):
    for h in range(H, 0, -1):
      if dp[h] != float('inf'):
        print(dp[h]+min(ab_li, key=lambda x:x[1])[1])
        break
  else:
    print(dp[-1])
  print(dp)
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

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

# 一番効率のよい魔法の探索
magic       = [list(map(int, input().split()))]
magic_cpmax = magic[0]
magic_cp    = magic[0][0] / magic[0][1]

# 一番効率のよい魔法の探索
for i in range(n-1):
  # 各魔法のリスト化
  magic.append(list(map(int, input().split())))
  # 効率のよい魔法の探索
  if(magic[i][0] / magic[i][1] > magic_cp):
    magic_cpmax = magic[i]
    magic_cp    = magic[i][0] / magic[i][1]

# モンスターをコスパが一番高い魔法で攻撃
q   = h // magic_cpmax[0]
mod = h % magic_cpmax[0]
ans = magic_cpmax[1] * q

# 倒せていたらそのまま出力
if(mod == 0):
  print(ans)
else:
  mp_min = magic_cpmax[1]
  for m in magic:
    if(m[0] >= mod & m[1] < mp_min):
      mp_min = m[1]
  print(ans + mp_min)

Submission status: Wrong Answer

Solution code:
import sys
import math
input=sys.stdin.readline
INF=10000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

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

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
info = [list(map(int, input().split())) for _ in range(n)]
info.sort(key=lambda x: (x[0] / x[1], -x[0]), reverse=True)
ene = 0
index = 0
def c(i, hh):
    s = float("inf")
    while i != n:
        tmp = abs(hh - info[i][0])
        if tmp < s:
            ans = i
            s = tmp
        i += 1
    return ans
    
while h > 0:
    ene += info[index][1]
    h -= info[index][0]
    if n != index + 1:
        if h - info[index][0] < 0:
            index += c(index, h) - index
print(ene)

Submission status: Wrong Answer

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

dp=[-1]*(h+maxA+5)
dp[0]=0
for i in range(1,h+maxA+5):
    for m in range(n):
        hp=M[m][0]
        mp=M[m][1]
        if i>=hp and dp[i-hp]!=-1: #体力より多い かつ 前の参照が存在しているとき
            if dp[i]==-1: #まだ更新されてないとき
                dp[i]=dp[i-hp]+mp
            else: #既に値があるとき
                dp[i]=(min(dp[i],dp[i-hp]+mp))

ans=h
while dp[ans]==-1:
    ans+=1
print(dp[ans])

Submission status: Wrong Answer

Solution code:
def sol():
    h,n=map(int,input().split())
    l=[]
    ans=10000000000007
    for i in range(n):
        a,b=map(int,input().split())
        l.append((a,b))
    d=[0]*20005
    for i in range(10002):
        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(10002):
        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 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())
AB = []

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

M = 2*10**4

dp = [[float('inf')]*(M+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    #print(dp[1])
    for j in range(H+1):
        dp[i+1][j+AB[i][0]] = min(dp[i][j+AB[i][0]],dp[i+1][j]+AB[i][1],dp[i+1][j+AB[i][0]])
        
ans = float('inf')
for i in range(H,M+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
x = []
d = []
amax = 1
for _ in range(n):
   a, b = map(int, input().split())
   x.append([a, b])
   d.append(a - b)
   amax = max(amax, a)


ans = 0
while (h >= amax):
   attack = d.index(max(d))
   h -= x[attack][0]
   ans += x[attack][1]


while(h > 0):
   y = [h - a - b for a, b in x]
   ymax = max(y)
   c = y.index(ymax)
   h -= x[c][0]
   ans += x[c][1]

print(ans)

Submission status: Wrong Answer

Solution code:
#E
import numpy as np
H, N = map(int, input().split())
a = []
b = []
a.append(10**9)
b.append(10**9)

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

dp = np.zeros((N+1,H+1))

a = np.array(a)
b = np.array(b)

#b *= -1

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

dp[0][0:H+2] = 10**9

#print(dp)

for i in range(1,N+1):
    dp[i][1:a[i]+1] = dp[i][0]
    for h in range(a[i]+1,H+1):
        #print(i,h)
        #if h > a[i]:
        #    dp[i][h] = min(dp[i][h-a[i]]+b[i],dp[i-1][h])
        #else:
        #    dp[i][h] = dp[i][h-1]
            #dp[i][h] = dp[i][0]
        dp[i][h] = min(dp[i][h-a[i]]+b[i],dp[i-1][h])

#print(dp)
#print('ans')
#print(dp)
print(int(dp[N][H]))

Submission status: Wrong Answer

Solution code:
W, N = map(int,input().split())
items = [[int(x) for x in reversed(input().split())] for _ in range(N)]
INF = 10 ** 12
dp = [[INF for i in range(W+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1): #1<= i <= N
        for j in range(1, W+1): # 1 <= j <= W
            dp[i][j] = min(dp[i-1][j], dp[i-1][max(j - items[i-1][1],0)] + items[i-1][0], dp[i][max(j - items[i-1][1],0)] + items[i-1][0])
print(dp[N][W])

Submission status: Wrong Answer

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**4+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**4+1):
        if i==0:
            if j < a[i]:
                dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i])
            else:
                dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], dp[i+1][j - a[i]] + b[i])
        else:
            if j < a[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]] + b[i])
print(dp[n][h])

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]

    INF = 10 ** 4 + 1
    D = [0 for _ in range(N)]

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

    res = min(D)
    print(res)





main()

Submission status: Wrong Answer

Solution code:
import numpy as np

h,n = map(int,input().split())
lst = []
for _ in range(n):
    a,b = map(int,input().split())
    lst.append([a,b,a/b])

lst.sort(key=lambda x:x[2], reverse=True)

num = h//lst[0][0]
rst = h - num*lst[0][0]
cnt = num*lst[0][1]

ans = np.inf
for i in range(n):
    num = h//lst[i][0]
    rst = h - num*lst[i][0]
    cnt = num*lst[i][1]
    
    if rst==0:
        ans = min(ans, cnt)
    else:
        ex = np.inf
        for j in range(n):
            if rst%lst[j][0]==0:
                ex_num = rst//lst[j][0]
            else:
                ex_num = rst//lst[j][0] + 1
            ex_cst = ex_num*lst[j][1]
            ex = min(ex, ex_cst)
        ans = min(ans, (ex+cnt))
print(ans)

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

DP = [[0] * (H+1) for i in range(N)]

for i in range(1,H+1):
    DP[0][i] = B[0] * -(-i//A[0])

for i in range(1,N):
    for j in range(1,H+1):
        if DP[i-1][j] < DP[i][max(1,j-A[i])] + B[i]:
            DP[i][j] = DP[i-1][j]
        else:
            DP[i][j] = DP[i][max(1,j-A[i])] + B[i]

print (DP[N-1][H])

Submission status: Wrong Answer

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

nums=[-1]*30001
for i in range(N):
  nums[AB[i][0]]=AB[i][1]
  
for i in range(1, H):
  if nums[i]>0:
    for j in range(N):
      if nums[i+AB[j][0]]>0 and nums[i+AB[j][0]]>nums[i]+AB[j][1]:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      if nums[i+AB[j][0]]<0:
        nums[i+AB[j][0]]=nums[i]+AB[j][1]
      
if nums[H]>0:
  print(nums[H])
else:
  i=1
  while nums[H+i]<0:
    i+=1
  print(nums[H+i])

Submission status: Wrong Answer

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

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

M = 2*10**4

dp = [[float('inf')]*(M+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    #print(dp[1])
    for j in range(H):
        dp[i+1][j+AB[i][0]] = min(dp[i][j+AB[i][0]],dp[i+1][j]+AB[i][1],dp[i+1][j+AB[i][0]])
        
ans = float('inf')
for i in range(H,M+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A, B = [], []
for i in range(N):
    tmp = list(map(int, input().split()))
    A.append(tmp[0])
    B.append(tmp[1])
    
dp = [[float("inf") for _ in range(H + 10)] for _ in range(N + 10)]
for i in range(N):
    dp[i][0] = 1

for i in range(N):
    for w in range(H):
        dp[i+1][w] = min(dp[i + 1][w], dp[i][w])
        if w >= A[i]:
            dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][w - A[i]] + B[i])
print(dp[N-1][H-1])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = list()
B = list()
eff = list()
for i in range(N):
  a_, b_ = map(int, input().split())  
  eff_ = a_ / b_
  A.append(a_)
  B.append(b_)
  eff.append(eff_)
  
best_ind = eff.index(max(eff))
num_of_best_attack = H // A[best_ind]
rest = H % A[best_ind]
ret = 0
if rest != 0:
  B_sorted = sorted(B)
  i = 0
  while True:  
    if A[B.index(B_sorted[i])] >= rest:
      ret = B_sorted[i]
      break
    i += 1
    if i == len(B) - 1:
      num_of_best_attack += 1
      ret = 0
      break
ret += num_of_best_attack * B[best_ind]
print(ret)

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]

i = np.argmax(A / B)

if H // A[i] == 0:
    print((H // A[i])*B[i])
else:
    j = np.argmin(B)
    print((H // A[i])*B[i] + B[j])

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

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

sum=0
while H>=1:
	eff = -1
	magic = 0
	attack = 0
	for Ai,Bi in zip(As,Bs):
		if H>Ai:
			if float(Ai)/float(Bi) >= eff:
				eff = float(Ai)/float(Bi)
				attack = Ai
				magic = Bi
		else:
			if float(H)/float(Bi) >= eff:
				eff = float(H)/float(Bi)
				attack = Ai
				magic = Bi
	H-=attack
	sum+=magic
print(sum)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

inf = 10**8

H, N = map(int, input().split())
A = [None] * N
B = [None] * N

for i in range(N):
    A[i], B[i] = map(int, input().split())

nap = [[None for _ in range(H+1)] for _ in range(N+1)]
# nap[0] = [inf for _ in range(H+1)]
for j in range(1, H+1):
    if j <= A[0]:
        nap[0][j] = B[0]
    else:
        nap[0][j] = inf
for i in range(N+1):
    nap[i][0] = 0
# nap = [[0 for _ in range(H+2)] for _ in range(N+1)]
# nap = [[None for _ in range(H+1)] for _ in range(N)]
# nap[0][0] = 0

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

# for i in range(N):
#     for j in range(H+1):
#         if i == 0:
#             if j <= A[0]:
#                 nap[i][j] = B[0]
#             else:
#                 nap[i][j] = 0

#         if j - A[i-1] < 0:
#             nap[i][j] = nap[i-1][j]
#         else:
#             nap[i][j] = min(nap[i-1][j-A[i-1] + B[i-1]], nap[i-1][j])

# print(np.array(nap))
print(nap[-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
ma = 0
for i in range(n):
    a, b = map(int, input().split())
    ma = max(ma, a)
    ab.append([a, b])
INF = 10 ** 9
dp = [[INF for i in range(h + ma + 1)] for j in range(n+1)]
ans = INF
for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(a, h + ma + 1):
        # print(dp[i + 1][j - a] + b)
        dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        if j >= h:
            ans = min(ans, dp[i + 1][j])
print(ans)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
lis = []
wari = 0
dam = 0
mp = 0
use = 0
for l in range(n):
    a, b = map(int, input().split())
    lis.append([a, b])
    if wari < a / b :
        wari = a / b
        dam = a
        mp = b
use = (h // dam) * mp
h = h % dam
if h != 0:
    for l in range(n):
        if h <= lis[l][0] and mp >= lis[l][1]:
            mp = lis[l][1]
else:
    mp = 0
print(use + mp)

Submission status: Wrong Answer

Solution code:
import sys

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

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

A_sorted = sorted(A, key=lambda x: x[2], reverse=True)
  
usedMP = 0
ind = 0
mini = sys.maxsize
for i in range(sys.maxsize):
  if  H <= 0 or ind > (N-1):
    break;
  elif A_sorted[ind][0] <= H:
    usedMP = usedMP + A_sorted[ind][1] 
    H = H - A_sorted[ind][0] 
    mini = sys.maxsize
  else:
    if A_sorted[ind][1] < mini:
      mini = A_sorted[ind][1]
    ind = ind + 1
    
if mini != sys.maxsize:
  usedMP = usedMP + mini

print(usedMP)

Submission status: Wrong Answer

Solution code:
input1 = input().split()
H,N = int(input1[0]),int(input1[1])

jumon = []
cospa_list = []
total_mp = 0

for _ in range(N):
    input2 = input().split()
    cospa = int(input2[0]) / int(input2[1])
    tmp = [int(input2[0]),int(input2[1])]
    jumon.append(tmp)
    cospa_list.append(cospa)
    

tmp = cospa_list.index(max(cospa_list))

total_mp += H // jumon[tmp][0] * jumon[tmp][1]

H = H % jumon[tmp][0]

jumon.sort()

for i in range(N):
    if H <= jumon[i][0]:
        total_mp += jumon[i][1]
        break
    
print(total_mp)

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

DP = [[0] * (H+1) for i in range(N)]

for i in range(1,H+1):
    DP[0][i] = B[0] * -(-i//A[0])

for i in range(1,N):
    for j in range(1,H+1):
        if DP[i-1][j] == 0:
            if DP[i-1][max(1,j-A[i])] > 0:
                DP[i][j] = DP[i][max(1,j-A[i])] + B[i]
        elif DP[i-1][j] < DP[i][max(1,j-A[i])] + B[i]:
            DP[i][j] = DP[i-1][j]
        else:
            DP[i][j] = DP[i][max(1,j-A[i])] + B[i]

print (DP[N-1][H])

Submission status: Wrong Answer

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

h, n = na()
a, b = [], []
for _ in range(n):
    ai, bi = na()
    a.append(ai)
    b.append(bi)
inf = 10**9
dp = [[inf]* (10**4+1) for _ in range(n+1)]
for i in range(n):
    for j in range(1, 10**4+1):
        if j < a[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],((j-1)//a[i]+1)*b[i], dp[i+1][j - a[i]] + b[i])
print(dp[n][h])

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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(float(A/B))
idx=np.argmax(c)
num=int(h/a[idx])
to=num*b[idx]


z=h%a[idx]
if z!=0:
    d=(-((-z)//(np.array(a))))
    e=d*np.array(b)
    to+=b[np.argmin(e)]
print(to)

Submission status: Wrong Answer

Solution code:
input1 = input().split()
H,N = int(input1[0]),int(input1[1])

jumon = []
cospa_list = []
total_mp = 0

for _ in range(N):
    input2 = input().split()
    cospa = int(input2[0]) / int(input2[1])
    tmp = [int(input2[0]),int(input2[1])]
    jumon.append(tmp)
    cospa_list.append(cospa)
    

tmp = cospa_list.index(max(cospa_list))

total_mp += H // jumon[tmp][0] * jumon[tmp][1]

#使用MP
print(total_mp)

#残りHP
H = H % jumon[tmp][0]
print(H)

jumon.sort()

print(jumon)

for i in range(N):
    if H <= jumon[i][0]:
        total_mp += jumon[i][1]
        break
    
print(total_mp)

Submission status: Wrong Answer

Solution code:
H, N = list(map(int,input().split()))

dmg = [0]*N
mp  = [0]*N
eff = [0]*N
mp_loss = 0

for i in range(N):
    dmg[i], mp[i] = list(map(int,input().split()))

def eff_culc(H):
    for i in range(N):
        eff[i] = min(H,dmg[i])/mp[i]
    max_idx = eff.index(max(eff))   
    return max_idx

while H > 0:
    max_idx = eff_culc(H)
    H = H - dmg[max_idx]
    mp_loss += mp[max_idx]
    
print(mp_loss)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AList = []
BList = []
CList = []
for i in range(N):
    A, B = map(int, input().split())
    AList.append(A)
    BList.append(B)
    CList.append(A / B)

ZIP = zip(CList, BList, AList)
ZIP = sorted(ZIP)

CList, BList, AList = zip(*ZIP)

print(AList, BList, CList)
i = N
tmp1 = 0
tmp2 = 0

Magic = 0

result = 0
while 'true':
    if H > AList[i - 1]:
        H -= AList[i - 1]
        result += BList[i - 1]
        print(H, result, AList[i - 1], BList[i - 1])
    else:
        tmp1 = BList[i - 1]
        ZIP = zip(BList, AList)
        ZIP = sorted(ZIP)
        BList, AList = zip(*ZIP)
        for q in range(0, N - 1):
            if H % AList[q] == 0:
                tmp2 = H // AList[q]
            else:
                tmp2 = H // AList[q] + 1
            Magic = tmp2 * BList[q]
            if tmp1 > Magic:
                tmp1 = Magic
        
        break

print(result + tmp1)

Submission status: Wrong Answer

Solution code:
def main():
    H, N = map(int, input().split())
    l = []
    for _ in range(N):
        a, b = map(int, input().split())
        l.append((a,b))
    dp = [[0] * N for _ in range(H)]
    for w in range(H):
        if (w+1) % l[0][0] == 0:
            dp[w][0] = l[0][1] * ((w+1)//l[0][0])
        else:
            dp[w][0] = l[0][1] * (1 + ((w+1)//l[0][0]))
    for i in range(1, N):
        for w in range(H):
            if w + 1 > l[i][0]:
                m = min(list(zip(*dp))[i][w-l[i][0]:w])
                dp[w][i] = min(m + l[i][1], dp[w][i-1])
            else:
                dp[w][i] = dp[w][i-1]
    print(min(dp[-1]))
main()

Submission status: Wrong Answer

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

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

dp = [[float("inf")]*(10**4+10**4) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(10**4):
        if j < lst1[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-lst1[i][0]]+lst1[i][1])

ans = 10**10
for i in range(h,len(dp[-1])):
    ans = min(ans,dp[-1][i])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
h, n = map(int, input().split())
magic = [
    list(map(int, input().split())) for i in range(n)
]
dp = np.full((n+1, h+1), np.inf)
dp[1:, 0] = 0
dp[1][1] = magic[0][0]
for i in range(1, n+1):
    for j in range(1, h + 1):
        if i == 1:
            dp[i][j] = magic[i-1][1] * np.ceil(j/magic[i-1][0])
        elif j >= magic[i-1][0]:
            dp[i][j] = min(
                dp[i-1][j], dp[i][j-magic[i-1][0]] + magic[i-1][1],
            )
        else:
            dp[i][j] = dp[i-1][j]
print(int(dp[n][h]))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

def solve():
    input = sys.stdin.readline
    H, N = map(int, input().split())
    M = [tuple(int(a) for a in input().split()) for _ in range(N)]
    DP = [[1000000000 for _ in range(H + 1)] for i in range(N + 1)]
    DP[0][0] = 0
    for i, m in enumerate(M):
        a, b = m
        for j in range(H + 1):
            if DP[i][j] < 1000000000:
                original = DP[i][j]
                DP[i+1][j] = min(DP[i+1][j], original)
                for d in range(1, 10000):
                    if j + d * a >= H:
                        DP[i+1][H] = min(DP[i+1][H], original + d * b)
                        break
                    else:
                        DP[i+1][j + d * a] = min(DP[i + 1][j + d * a], original + d * b)
    print(DP[N][H])


    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

dp=[-1]*(h+a+5)
dp[0]=0
for i in range(1,h+a+5):
    for m in range(n):
        hp=M[m][0]
        mp=M[m][1]
        if i>=hp and dp[i-hp]!=-1: #体力より多い かつ 前の参照が存在しているとき
            if dp[i]==-1: #まだ更新されてないとき
                dp[i]=dp[i-hp]+mp
            else: #既に値があるとき
                dp[i]=(min(dp[i],dp[i-hp]+mp))

ans=h
while dp[ans]==-1:
    ans+=1
print(dp[ans])

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(N)]
AB.sort(key=lambda x: x[1])
AB.sort(key=lambda x: float(x[0])/x[1],reverse=True)
C = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(N):
        remain = H-AB[i][0]
        if remain <= 0:
            C[i][j] = AB[i][1]
            continue
        if remain%AB[j][0] == 0:
            factor = remain//AB[j][0]
        else:
            factor = remain//AB[j][0]+1
        C[i][j] = AB[i][1] + factor*AB[j][1]
ans = 10**10
for i in range(N):
    for j in range(N):
        ans = min(ans,C[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
magic = []
for _ in range(N):
    magic.append(list(map(int,input().split())))
for i in range(N):
    magic[i].append(magic[i][0]/magic[i][1])
max_eff = 0
max_i = -1
for i in range(N):
    if max_eff<magic[i][2]:
        max_eff = magic[i][2]
        max_i = i

cnt = H//magic[max_i][0]
ans = magic[max_i][1]*cnt
if H%magic[max_i][0]==0:
    print(ans)
else:
    nokori = H - magic[max_i][0]*cnt
    nn = []
    for i in range(N):
        if nokori - magic[i][0]<=0:
            nn.append(magic[i])
    min_eff = 10000
    for i in range(len(nn)):
        if min_eff>nn[i][1]:
            min_eff = nn[i][1]
    ans += nn[i][1]
    print(ans)

Submission status: Wrong Answer

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

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

M = H+1

dp = [[float('inf')]*(M+1) for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

for i in range(N):
    #print(dp[1])
    for j in range(M+1):
        dp[i+1][min(j+AB[i][0],H+1)] = min(dp[i][min(j+AB[i][0],H+1)],dp[i+1][j]+AB[i][1],dp[i+1][min(j+AB[i][0],H+1)])
        
ans = float('inf')
for i in range(H,M+1):
    ans = min(ans,dp[N][i])
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

H,N = map(int,input().split())
A = [0]*N
B = [0]*N
E = [[0,0] for i in range(N)]
for i in range(N):
    A[i],B[i] = map(int,input().split())
ans = 0

while(H > 0):
    for i in range(N):
        A[i] = min(H,A[i])
        E[i] = [-A[i]/B[i],i]
    heapq.heapify(E)
    H -= A[E[0][1]]
    ans += B[E[0][1]]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h, n = map(int, input().split())
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append([a, b])
INF = 10 ** 9
dp = [[INF for i in range(2 * h + 1)] for j in range(n+1)]
ans = INF
for i, (a, b) in enumerate(ab):
    dp[i + 1][0] = 0
    for j in range(a, 2 * h + 1):
        # print(dp[i + 1][j - a] + b)
        dp[i + 1][j] = min(dp[i + 1][j - a] + b, dp[i][j])
        if j >= h:
            ans = min(ans, dp[i + 1][j])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    h,n=MI()
    l=[]
    for i in range(n):
        a,b=MI()
        l.append([a,b])
    l.sort(key=lambda x: x[0])
    dp=[[0 for i in range(h)] for j in range(n+1)]
    for i in range(h):
        dp[n][i]=100000000
    for j in range(n):
        for i in range(h):
            a,b=l[j][0],l[j][1]
            # print(a,b,i,j)
            if (i+1)<=a:
                dp[j][i]=b
            else:
                x = (i+1)//a
                # print(x)
                r = (i+1)%a
                # print(r)
                if r!=0:
                    s = x*b + dp[n][r-1]
                else:
                    s=x*b
                # print(s)
                dp[j][i]=s
            
            # print(dp[j][i],dp[n][i])
    # print(dp)
    print(dp[n][h-1])

if __name__ == "__main__":
    main()

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())
usedmp = 0
C = [a/b for (a,b) in zip(A,B)]
max_value = max(C)
max_index = C.index(max_value)
while h > A[max_index]:
    h -= A[max_index]
    usedmp += B[max_index]
B2 = []
for i in range(n):
    if A[i] >= h:
        B2.append(B[i])
usedmp += min(B2)
print(usedmp)

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())
usedmp = 0
C = [a/b for (a,b) in zip(A,B)]
max_value = max(C)
max_index = C.index(max_value)
while h > A[max_index]:
    h -= A[max_index]
    usedmp += B[max_index]
B2 = []
for i in range(n):
    if A[i] >= h:
        B2.append(B[i])
usedmp += min(B2)
print(min(B2))
print(usedmp)