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:
import sys
import math
read = sys.stdin.buffer.read #全てまとめて文字列として格納
readline = sys.stdin.buffer.readline # 一行読む
readlines = sys.stdin.buffer.readlines # 全行リストに格納
H,N = map(int, readline().split())
AB = [map(int, line.split()) for line in readlines()]

i = 0
A=[]
B=[]
kosupa = []
for AA,BB in AB:
  A.append(AA)
  B.append(BB)
  kosupa.append(AA/BB)
  i+=1
saikyo_index = kosupa.index(max(kosupa))
if H % A[saikyo_index] == 0:
  print(int(H/A[saikyo_index])*B[saikyo_index])
else:
  syohi = math.floor(H/A[saikyo_index])*B[saikyo_index]
  todome=0
  nokorihp = H - A[saikyo_index]*math.floor(H/A[saikyo_index])
  indexmemo = 0
  lastsyohi=9999999999
  for AAA,BBB in zip(A,B):
    for j in range(1, 100):
      if AAA*j >= nokorihp:
        if BBB*j < lastsyohi:
          todome=indexmemo
          lastsyohi = BBB*j
    indexmemo+=1
  syohi += B[todome]
  print(syohi)

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 = num_of_best_attack * B[best_ind]
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
print(ret)

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+=np.min(e)
print(to)

Submission status: Wrong Answer

Solution code:
import math
h,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

mini=0
maryoku=0
mahou=0
for i in range(n):
    #コスパの良い魔法を探す
    if mini<=l[i][0]/l[i][1]:
        mini=l[i][0]/l[i][1]
        maryoku=l[i][1]
        mahou=l[i][0]#威力

nokori=h-(h//mahou)*mahou
ans=(h//mahou)*maryoku

if nokori==0:
    print(ans)
    exit()

min_m=maryoku
for i in range(n):
    if nokori<=l[i][0] and l[i][1]<=maryoku:
        if min_m>=l[i][0]:
            min_m=l[i][1]

    elif nokori>l[i][0]:
        if math.ceil(nokori/l[i][0])*l[i][1]<=maryoku:
            if min_m>=math.ceil(nokori/l[i][0])*l[i][1]:
                min_m=math.ceil(nokori/l[i][0])*l[i][1]

print(ans+min_m)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 12
dp = [INF for _ in range(h + 1)]
dp[0] = 0
for a, b in m:
    for i in range(h + 1):
        if i + a > h:
            dp[h] = min(dp[h], dp[i] + b)
            break
        else:
            dp[i + a] = min(dp[i + a], dp[i] + b)
print(dp[h])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A = [0] * N # damage
B = [0] * N # MP
for i in range(N):
    A[i], B[i] = map(int, input().split())

# H = 9999
# N = 10
# A = [540,691,700,510,]
# B = [3,2,1]

ans = 0

# ------------------------------------------------
ansAmari = float("inf")
def saiki(damage, consumedMP):
    global ansAmari
    if damage >= Hamari:
        ansAmari = min(ansAmari, consumedMP)
        return
        
    for j in range(N):
        saiki(damage+A[j], consumedMP+B[j])
# ------------------------------------------------

cospa = 0
cospaList = []
for x in range(N):
    cospaList.append(A[x]/B[x])
    cospa = max(A[x]/B[x], cospa)
# print(cospa)
# print(cospaList)

cospaBanchi = []
for x in range(N):
    if cospaList[x] == cospa:
        cospaBanchi.append(x)
        
saisyoDamage = 0
saisyoConsumeMP = float("inf")
for y in cospaBanchi:
    saisyoConsumeMP = min(saisyoConsumeMP, B[y])
    if saisyoConsumeMP == B[y]:
        saisyoDamage = A[y]
        
# shou = H // saisyoConsumeMP
# print(shou)
ans += (H // saisyoDamage)*saisyoConsumeMP

Hamari = H % saisyoDamage
# print(amari)
if Hamari == 0:
    print(ans)
else:
    saiki(0,0)
    print(ans+ansAmari)

Submission status: Wrong Answer

Solution code:
import numpy as np
def find_nearest(array, value):
	array = np.asarray(array)
	idx = (np.abs(array - value)).argmin()
	return array[idx]
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)
#print(A,B)
C = []
for i in range(N):
	C.append(B[i]/A[i])
m_min = min(C)
#print(C)
#print(C.index(m_min))

sum = 0
while H>0:
	if(H < max(A)):
		num_index = A.index(find_nearest(A,H))
		
		hikaku = H / min(C)
		hikaku = int(np.ceil(hikaku))
		if(B[num_index] <= hikaku * B[C.index(m_min)]):
			sum += B[num_index]
			break
	sum += B[C.index(m_min)]
	H -= A[C.index(m_min)]
print(sum)

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])
    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:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
e = enumerate

sys.setrecursionlimit(10**7)
def main():
    H, N = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

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

    for i, ab in e(AB):
        a, b = ab[0], ab[1]
        for j in range(H+1):

            if j==0:
                newval = b
            elif j%a==0:
                newval = j//a * b
            else:
                newval = (j//a+1) * b

            if j>=a:
                newval2 = dp[i][j-a] + b
            else:
                newval2 = INF

            if j>=a:
                newval3 = dp[i+1][j-a] + b
            else:
                newval3 = INF

            dp[i+1][j] = min(dp[i][j], newval, newval2, newval3)

    print(dp[N][H])

if __name__ == '__main__':
    main()

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

Submission status: Wrong Answer

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

dp = [[10 ** 9] * (h + 1) for i in range(n + 1)]

for i in range(n):
    count = 1
    for j in range(1, h + 1):
        if j % ab[i][0] == 0:
            dp[i + 1][j] = ab[i][1] * count
            count += 1

for i in range(n + 1):
    for j in range(h + 1):
        if i < n:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            dp[i + 1][min(h, j + ab[i][0])] = min(dp[i + 1][min(h, j + ab[i][0])], dp[i][j] + ab[i][1])
        if i > 0:
            dp[i][min(h, j + ab[i - 1][0])] = min(dp[i][min(h, j + ab[i - 1][0])], dp[i][j] + ab[i - 1][1])

print(dp[n][h])

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
w = []
v = []
for i in range(n):
    w_, v_ = map(int, input().split())
    w.append(w_)
    v.append(v_)
#W = int(input())

dp = [[0] * (h + 1) for i in range(n + 1)]

for i in range(n):
    for j in range(h + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])

print(dp[n][h])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
dp = [float('inf') for _ in range(H+1)]

for i, ab in enumerate(AB):
    a, b = ab
    j = 1
    while j * AB[i][0] <= H:
        dp[AB[i][0] * j] = min(dp[AB[i][0] * j], AB[i][1] * j)
        j += 1

for h in range(H):
    for n in range(N):
        j = 1
        while j * AB[n][0] <= H:
            if h + AB[n][0] * j >= H:
                dp[H] = min(dp[H], dp[h] + AB[n][1] * j)
                break
            else:
                dp[h + AB[n][0] * j] = min(dp[h + AB[n][0] * j], dp[h] + AB[n][1] * j)
            j += 1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
hn = list(map(int, input().split()))
h = hn[0]
n = hn[1]

magic = []
for i in range(n):
    magic.append(list(map(int, input().split())))

magic = sorted(magic)

c = [[0] * (h + 1) for i in range(n)]

l = 0
while(l < h):
    l += magic[0][0]
    if l > h:
        m = h
    else:
        m = l
    c[0][m] = c[0][l-magic[0][0]] + magic[0][1]

for i in reversed(range(len(c[0]))):
    if c[0][i-1] == 0:
        c[0][i-1] = c[0][i]

for i in range(1, n):
    for j in range(h+1):
        if j + magic[i][0] > h:
            k = h
        else:
            k = j

        if j - magic[i][0] >= 0:   
            if c[i-1][k] > c[i][j-magic[i][0]] + magic[i][1]:
                c[i][k] = c[i][j-magic[i][0]] + magic[i][1]
            else:
                c[i][k] = c[i-1][j]

        else:
            c[i][k] = c[i-1][j]

print(c[-1][-1])

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=[]
for i in range(H):
    J.append([int(x) for x in input().split()])
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)
print(min(ff))

Submission status: Wrong Answer

Solution code:
import math
H,N=map(int,input().split())
A=[]
B=[]
eff=[]
mp=0

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

while H!=0:
    eff_max_index=eff.index(max(eff))
    tmp=math.floor(H/A[eff_max_index])
    H-=tmp*A[eff_max_index]
    mp+=tmp*B[eff_max_index]
    for i in range(N):
        if A[i]>H:
            A[i]=H
            eff[i]=A[i]/B[i]
print(mp)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
li = []
for i in range(n):
  a = list(map(int,input().split()))
  li.append(a)
li_a = sorted(li)
c = n
g = 0
li_c = []
while h > 0:
  li_b = []
  for i in range(c):
    li_b.append(li_a[i][0]/li_a[i][1])
  b = max(li_b)
  c = li_b.index(b)
  d = li_a[c][0]
  e = li_a[c][1]
  while h > d:
    h -= d
    g += e
  li_c.append(g+e)
  if c == 0:
    break
print(min(li_c))

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
List=[]
A=0
B=0
C=10*10*10*10
D=0
for i in range(N):
    a,b=list(map(int,input().split()))
    c=a/b
    List.append((a,b,c))
sortsecond=lambda val: val[2]
List1=sorted(List,key=sortsecond)
List2=sorted(List)
for i in range(H):
    if A<H:
        h=H-A
        if h>=List1[N-1][0]:
            A=A+List1[N-1][0]
            B=B+List1[N-1][1]
        else:
            for j in range(N):
                if List2[j][0]>=h:
                    temp1=List2[j][0]
                    temp=List2[j][1]
                    if temp<=C:
                        C=temp
                        D=temp1
            B=B+C
            A=A+D
    elif A>=H:
        break
print(B)

Submission status: Wrong Answer

Solution code:
H, N = list(map(int, input().split()))
w = []
v = []
for _ in range(N):
    v1, w1 = list(map(int, input().split()))
    w.append(w1)
    v.append(v1)
    
INF = 1e15
dp = [[INF]*(H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for j in range(H+1):
    c = j//v[0]*w[0]
    if j%v[0]!=0:
        c += w[0]
    dp[1][j] = c

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

Submission status: Wrong Answer

Solution code:
def sol():
    h,n=map(int,input().split())
    l=[]
    #ans=10000000000007
    ans=0
    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 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=[]
B=[]
amount=0
while N>0:
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
    N-=1

while H>0:
    temp = min(A, key=lambda x:abs(x-H))
    amount += B[A.index(temp)]
    H-= A[A.index(temp)]

print(amount)

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# import numpy as np

inf = 10**8
# inf = np.inf

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)]
# 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
        nap[0][j] = nap[0][j-A[0]] + B[0]
for i in range(N):
    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):
    for j in range(H+1):
        if j - A[i] < 0:
            nap[i][j] = nap[i-1][j]
        else:
            # print(np.array(nap))
            # print(i, j)
            nap[i][j] = min(nap[i-1][j-A[i]] + B[i], nap[i-1][j], nap[i][j-A[i]] + B[i])

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

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def dc(n, m):
    return -(-n // m)

# @mt
def slv(H, N, AB):
    ans = 0
    abc = [(a/b, b, a) for a, b in AB]

    abc.sort(key=lambda x: x[1])
    abc.sort(key=lambda x: x[2])
    abc.sort(key=lambda x: x[0], reverse=True)
    ri = set()
    for i in range(1, N):
        if abc[i][1] >= abc[i-1][1]:
            ri.add(i)
    ri = set(ri)
    abc_ = []
    for i in range(N):
        if i not in ri:
            abc_.append(abc[i])
    abc = abc_
    error_print(len(abc))
    HD = defaultdict(lambda : INF)
    _, b, a = abc[0]
    for i in range(1, dc(H, a)+1):
        HD[H - i*a] = i*b
    for _, b, a in abc[1:]:
        for k, v in reversed(list(HD.items())):
            for i in range(1, dc(k, a)+1):
                if HD[k - i*a] > v+i*b:
                    HD[k- i*a] = v+i*b
                else:
                    break
    ans = INF
    for k, v in HD.items():
        if k <= 0:
            ans = min(ans, v)


    return ans


def main():
    H, N = read_int_n()
    AB = [read_int_n() for _ in range(N)]
    print(slv(H, N, AB))
    # H = 10**4
    # N = 1000
    # AB = [[random.randint(1, 100), random.randint(1, 10000)] for _ in range(N)]
    # print(slv(H, N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H, N = input().split(" ")
H, N = int(H), int(N) 
data = []
for i in range(N):
    a, b = input().split(" ")
    a, b = int(a), int(b)
    data.append((a, b, float(a/b)))

data = sorted(data, key=lambda t: t[0], reverse=True) # Aを元に並べ替え
data = sorted(data, key=lambda t: t[2], reverse=True) # rateを元に並べ替え
_idx = 0 
accum = 0
a = data[0][0]
b = data[0][1]
while a <= H:
    H -= a 
    accum += b
if H <= 0:
    print(accum)
else:
    data = sorted(data, key=lambda t:H%t[0])
    a = data[0][0]
    b = data[0][1]
    while H > 0:
        H -= a
        accum += b
    print(accum)

Submission status: Wrong Answer

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)
        if j + a >= H:
            dp[H] = min(dp[H], dp[j] + b)

answer = dp[H]
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
W, N = map(int,input().split())
items = [[int(x) for x in reversed(input().split())] for _ in range(N)]
INF = 10 ** 4
dp = [[INF for i in range(W+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][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:
H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]

nums=[-1]*30001
for i in range(N):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][1], nums[AB[i][0]])
  
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())

waza = []
cospa = []

cospa = 0 # コスパのいい技計算用
cost = 0 # コスト
for i in range(N):
    a, b = map(int, input().split())
    waza.append({"A":a, "B":b})
    
    # コスパのいい技判定
    if waza[cospa]["A"]/waza[cospa]["B"] < a/b:
        cospa = i
        #print("コスパ技変更: ", waza[cospa]["A"],waza[cospa]["B"])

# Attack
for i in range(10**5):
    #print("体力:", H)
    
    """
    
    # コスパ技再計算
    tmp = [n for n in range(N) if waza[n]["A"] < H]
    _cospa = min(tmp) if len(tmp) else 0
    #print("暫定コスパ:", _cospa)
    for _waza in waza:
        if waza[_cospa]["A"]/waza[_cospa]["B"] < _waza["A"]/_waza["B"] and _waza["A"] < H:
            cospa = l
            #print("コスパ技変更: ", waza[cospa]["A"],waza[cospa]["B"])
    """
    
    # コスパの技以上の体力なら、コスパ技を出す
    if H >= waza[cospa]["A"]:
        H -= waza[cospa]["A"]
        cost += waza[cospa]["B"]
    # 体力0なら倒した
    elif H==0:
        break
    else:
        # ちょうどいい技を出す
        #最小コストで1撃
        tmp = [w for w in waza if w["A"] >= H]
        seq = [x['B'] for x in tmp]
        #print("min", min(seq))
        # 倒す
        H = 0
        cost += min(seq)
    

#print("=====")
print(cost)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
max=[]
for _ in range(M):
    a, b = map(int, input().split())
    max.append(a-b)
m=0
for i in range(M):
  if m<max[i]:
    m=max[i]
    q=i
p=1
while N-m*p>0:
  p+=1
print(m*p)

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])
  
if __name__ == '__main__':
  run()

Submission status: Wrong Answer

Solution code:
import copy
h, n = map(int, input().split())
all_l = []
all_l_2 = []
for i in range(n):
    a_tmp, b_tmp = map(int, input().split())
    all_l.append([a_tmp/b_tmp, -a_tmp, b_tmp])
    all_l_2.append([b_tmp, -a_tmp])

all_l.sort()
all_l = all_l[::-1]
all_l_2.sort()
ans = 0
i = 0
t=0
while h>0:
    ns = h//(-all_l[i][1])
    ans += all_l[i][2] * ns
    h -= -all_l[i][1]*ns
    i+=1
    if h ==0:
        print(ans)
        exit()
    for j in range(n):
        if -all_l_2[j][1] >=h:
            ans += all_l_2[j][0]
            print(ans)
            exit()

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
    print(int(count+todomeMP))

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

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

if n == 1:
  print(ceil(h/l[0][0]) * l[0][1])
  exit(0)

dp = [ceil(hp/l[0][0]) * l[0][1] for hp in range(h + 1)] + ([10 ** 9] * (10 ** 4))

for i in range(1, n):
  for hp in range(h + 1):
    dp[hp] = min([dp[hp], dp[hp - l[i][0]] + l[i][1]])

print(dp[h])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[]
b=[]
for i in range(n):
  aa,bb=map(int,input().split())
  a.append(aa)
  b.append(bb)
inf=10**10
f=h+max(a)+1
dp=[f*[inf]for _ in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
  dp[i][0]=0
  for j in range(f-a[i-1]):
    dp[i][j+a[i-1]]=min(dp[i-1][j+a[i-1]],dp[i][j]+b[i-1])
print(min(dp[-1][h:]))

Submission status: Wrong Answer

Solution code:
import sys
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)
INF = 1 << 29
# 動的計画法？
dp_H = H + 100
dp_N = N + 10
dp = [[INF for _ in range(dp_H)] for _ in range(dp_N)]
for i in range(N):
    dp[i][0] = 0

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

if dp[N][H] != INF:
    print(dp[N][H])
    sys.exit(0)

for i in range(H,-1,-1):
    if dp[N][i] != INF:
        print(dp[N][i] + 1)
        sys.exit(0)

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):
  if nums[AB[i][0]]<0:
    nums[AB[i][0]]=AB[i][1]
  else:
    nums[AB[i][0]]=min(AB[i][0], nums[AB[i][0]])
  
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 = [int(i) for i in input().split()]
A=[]; B=[]
for _ in range(N):
    a, b = [int(i) for i in input().split()]
    A.append(a); B.append(b)

# A : value  B : weight
INF = 10**9
dp = [[INF for _ in range(20010)] for _ in range(N+10)]

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

for i in range(N):
    for w in range(H+10000):
        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][H])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H, N = list(map(int, input().split()))
w = []
v = []
for _ in range(N):
    v1, w1 = list(map(int, input().split()))
    w.append(w1)
    v.append(v1)
    
INF = 1e10
dp = [[INF]*(H+1) for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for j in range(H+1):
    c = j//v[0]*w[0]
    if j%v[0]!=0:
        c += w[0]
    dp[1][j] = c

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

Submission status: Wrong Answer

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

cost_perfomance=[]

for i in range(N):
    cost_perfomance.append(A[i]/B[i])

good_cost_idx=cost_perfomance.index(max(cost_perfomance))
good_cost_magic_power=A[good_cost_idx]

gcmp_num=H//good_cost_magic_power
cost=gcmp_num*B[good_cost_idx]

last_HP=H-gcmp_num*good_cost_magic_power

if last_HP>0:
    matome=[j for i,j in zip(A,B) if i>=last_HP]
    print(cost+min(matome))
else:
    print(cost)

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]
#for j in range(H+1):
#    dp[0][j] = 10**9
dp[0][:] = 10**9

#print(dp)

for i in range(1,N+1):
    dp[i][1:a[i]] = dp[i][0]
    for h in range(a[i],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:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+1):
        if dp[j-a] == INF:
            continue
        if j + a > H:
            dp[H] = min(dp[H], dp[j] + b)
        dp[j] = min(dp[j], dp[j-a] + b)

answer = dp[H]
print(answer)

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])
while H > 0:
	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 numpy as np
import sys
input = sys.stdin.readline


def main():

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

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

    m = 2 * 10**4 + 10
    dp = [0] * m
    for a, b in zip(A, B):
        dp[a] = b
    for i in range(10**4 + 1):
        for a, b in zip(A, B):
            # if i + a < 10**4:
            # print(i + a)
            # print(dp[i], dp[i + a], b, i + a)
            if i + a < m and dp[i] > 0:
                if dp[i + a] > 0:
                    dp[i + a] = min(dp[i + a], dp[i] + b)
                else:
                    dp[i + a] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    d = np.array(dp[k:])
    print(np.min(d[d.nonzero()]))


main()