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 numpy as np


def read():
    H, N = list(map(int, input().strip().split()))
    AB = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        AB.append((a, b))
    return H, N, AB


def solve(H, N, AB, INF=10**9):
    BMAX = 10**4
    dp = np.empty(H + BMAX + 1, dtype=np.int32)
    dp[:] = INF
    dp[0] = 0
    
    for h in range(0, H + BMAX + 1):
        for a, b in AB:
            if h - a >= 0:
                dp[h] = min(dp[h], dp[h - a] + b)
    return dp[H]


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from collections import deque


def read():
    H, N = list(map(int, input().strip().split()))
    A = list()
    B = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return H, N, A, B


def solve(H, N, A, B, INF=1000000):
    BMAX = max(B)
    dp = [[INF for i in range(N)] for h in range(H + BMAX + 1)]
    for i in range(0, N):
        dp[0][i] = 0
    for h in range(0, H + BMAX + 1):
        for i in range(N):
            if i == 0:
                if h - A[i] >= 0:
                    dp[h][i] = dp[h - A[i]][i] + B[i]
            else:
                if h - A[i] >= 0:
                    dp[h][i] = min(dp[h][i-1], dp[h - A[i]][i] + B[i])
                else:
                    dp[h][i] = dp[h][i-1]
    min_b = INF
    for h in range(H, H + BMAX + 1):
        for i in range(N):
            min_b = min(min_b, dp[h][i])
    return min_b


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
from collections import deque


def read():
    H, N = list(map(int, input().strip().split()))
    A = deque()
    B = deque()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return H, N, A, B


def solve(H, N, A, B, INF=1000000):
    BMAX = max(B)
    dp = [[INF for i in range(N)] for h in range(H + BMAX + 1)]
    for i in range(0, N):
        dp[0][i] = 0
    for h in range(0, H + BMAX + 1):
        for i in range(N):
            if i == 0:
                if h - A[i] >= 0:
                    dp[h][i] = dp[h - A[i]][i] + B[i]
            else:
                if h + A[i] >= 0:
                    dp[h][i] = min(dp[h][i-1], dp[h - A[i]][i] + B[i])
                else:
                    dp[h][i] = dp[h][i-1]
    min_a = INF
    for h in range(H, H + BMAX + 1):
        for i in range(N):
            min_a = min(min_a, dp[h][i])
    return min_a


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Wrong Answer

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


for j in range(n):
    for i in range(h):
        k=min(i+X[j][0],h)
        dp[k]=min(dp[k],dp[i]+X[j][1])
print(dp[h])

Submission status: Wrong Answer

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


for i in range(h):
    for j in range(n):
        k=min(i+X[j][0],h)
        dp[k]=min(dp[k],dp[i]+X[j][1])
print(dp[h])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
H=[]
A=[]
for i in range(n):
    a,b=map(int,input().split())
    H.append([a,b])
    A.append(a)
a_max=max(A)
dp=[10**5]*(h+a_max+1)
dp[0]=0
for i in range(1,h+a_max+1):
    for j in range(n):
        if i-H[j][0]<0:
            dp[i]=min(dp[i],H[j][1])
        else:
            dp[i]=min(dp[i],dp[i-H[j][0]]+H[j][1])
print(min(dp[h:h+a_max+1]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
H=[]
A=[]
for i in range(n):
    a,b=map(int,input().split())
    H.append([a,b])
    A.append(a)
a_max=max(A)
dp=[10**5]*(h+a_max+1)
dp[0]=0
for i in range(1,h+a_max+1):
    for j in range(n):
        if i-H[j][0]<0:
            continue
        dp[i]=min(dp[i],dp[i-H[j][0]]+H[j][1])
print(min(dp[h:h+a_max+1]))

Submission status: Wrong Answer

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

max_a = max(a)[0]

dp = [float('inf') for i in range(h + max_a + 1)]
dp[0] = 0
for i in range(1, h+max_a + 1):
    dp[i] = min(dp[i-x]+y for x,y in a)

print(dp[h])

Submission status: Wrong Answer

Solution code:
H, N = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]
inf = float("inf")
dp = [[inf] * (H*2) for _ in range(N+1)]
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(H*2):
        if j-AB[i][0] >= 0:
            dp[i+1][j] = min(dp[i+1][j-AB[i][0]]+AB[i][1], dp[i][j]) 
        else:
            dp[i+1][j] = dp[i][j]
ans = inf
for i in range(H,2*H):
    ans = min(ans, dp[-1][i])
print(ans)

Submission status: Wrong Answer

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

#dp[i][h]:i番目の魔法まで見てhのダメージを与えるときの最小魔力
dp = [[10**7+1 for j in range(H+1)] for i in range(N+1)]
dp[0][0] = 0

#配るdpで考える
for i in range(N):
  for h in range(H+1):
    #i番目の魔法を使わないとき
    dp[i+1][h] =  min(dp[i][h], dp[i+1][h])
    #i番目の魔法を一個使うとき
    dp[i+1][ min(h+l[i][0],H) ]  = min(dp[i+1][min(h+l[i][0],H)],dp[i+1][h]+l[i][1] )   
print(dp[N][H])

Submission status: Wrong Answer

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

#dp[i][h]:i番目の魔法まで見てhのダメージを与えるときの最小魔力
dp = [[10**4+1 for j in range(H+1)] for i in range(N+1)]
dp[0][0] = 0

#配るdpで考える
for i in range(N):
  for h in range(H+1):
    #i番目の魔法を使わないとき
    dp[i+1][h] =  min(dp[i][h], dp[i+1][h])
    #i番目の魔法を一個使うとき
    dp[i+1][ min(h+l[i][0],H) ]  = min(dp[i+1][min(h+l[i][0],H)],dp[i+1][h]+l[i][1] )   
print(dp[N][H])

Submission status: Wrong Answer

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

#dp[i][h]:i番目の魔法まで見てhのダメージを与えるときの最小魔力
dp = [[10**4+1 for j in range(H+1)] for i in range(N+1)]
dp[0][0] = 0

#配るdpで考える
for i in range(N):
  for h in range(H):
    #i番目の魔法を使わないとき
    dp[i+1][h] =  min(dp[i][h], dp[i+1][h])
    #i番目の魔法を一個使うとき
    dp[i+1][ min(h+l[i][0],H) ]  = min(dp[i+1][min(h+l[i][0],H)],dp[i+1][h]+l[i][1] )   
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 1000000

def main():
    h, n = list(map(int, input().strip().split()))
    a = [0] * (n+1)
    b = [0] * (n+1)
    for i in range(1, n+1):
        a[i], b[i] = list(map(int, input().strip().split()))
    dp = [[INF] * (2 * 10**4 + 5) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = 0
    for i in range(1, n+1):
        for j in range(1, 2 * 10**4 + 5):
            if j-a[i] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-a[i]] + b[i])
    ans = INF
    print(min(dp[n][h:]))
    # for i in range(n+1):
    #     for j in range(h+10):
    #         print("{} ".format(dp[i][j]), end='')
    #     print('')
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# abc153 e

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
h, n = map(int, input().split())
x = [[]] * n
for i in range(n):
    a, b = map(int, input().split())
    c = 0
    x[i] = [c, a, b]

ans = 0
while h > 0:
    for i in range(n):
        x[i][0] = min(h, x[i][1]) / x[i][2]
    x.sort(reverse=True)
    # print(h, ans, x)
    if h > x[0][1]:
        ans += x[0][2] * (h // x[0][1])
        h %= x[0][1]
        # print(h, x)
    else:
        ans += x[0][2]
        h -= x[0][1]
        # print(h, ans, x)
        # print(h, x)
print(ans)

Submission status: Wrong Answer

Solution code:
# abc153 e

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
h, n = map(int, input().split())
x = [[]] * n
for i in range(n):
    a, b = map(int, input().split())
    c = 0
    x[i] = [c, a, b]

ans = 0
while h > 0:
    for i in range(n):
        x[i][0] = min(h, x[i][1]) / x[i][2]
    x.sort(reverse=True)
    print(h, ans, x)
    if h > x[0][1]:
        ans += x[0][2] * (h // x[0][1])
        h %= x[0][1]
        # print(h, x)
    else:
        ans += x[0][2]
        h -= x[0][1]
        print(h, ans, x)
        # print(h, x)
print(ans)

Submission status: Wrong Answer

Solution code:
# abc153 e

import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(4100000)
INF = 1 << 60
MOD = 10 ** 9 + 7

# ここから書き始める
h, n = map(int, input().split())
x = [[]] * n
for i in range(n):
    a, b = map(int, input().split())
    c = max(h, a) / b
    x[i] = [c, a, b]
#     c = a / b
#     x[i] = [a, b, c]
# print(x)
# index = -1
# maximum_c = -INF
# for i in range(n):
#     if x[i][2] > maximum_c:
#         index = i

ans = 0
while h > 0:
    for i in range(n):
        x[i][0] = min(h, x[i][1]) / x[i][2]
    # if h > x[0][1]:
    #     h %= x[0][1]
    x.sort(reverse=True)
    # print(h, x)
    if h > x[0][1]:
        ans += x[0][2] * (h // x[0][1])
        h %= x[0][1]
    # if h > x[0][1]:
    #     h %= x[0][1]
    else:
        ans += x[0][2]
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]
        for j in range(H-a+1):
            if a >= H:
                mp_for_damage[H] = min(mp_for_damage[H], b)
                continue

            if a < H and mp_for_damage[a] < b:
                continue

            for k in range(1, min(a, H)+1):
                mp_for_damage[k] = min(mp_for_damage[k], b)
                #print(k, b)

            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()

Submission status: Wrong Answer

Solution code:
import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]
        for j in range(H-a+1):
            if a < H and mp_for_damage[a] < b:
                continue

            for k in range(1, min(a, H)+2):
                mp_for_damage[k] = min(mp_for_damage[k], b)
                #print(k, b)

            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()

Submission status: Wrong Answer

Solution code:
import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]
        for j in range(H-a+1):
            if a < H and mp_for_damage[a] < b:
                continue

            for k in range(1, min(a, H)):
                if k > H:
                    break
                mp_for_damage[k] = min(mp_for_damage[k], b)

            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()

Submission status: Wrong Answer

Solution code:
import math

h,n = map(int,input().split())
a = [] ; b = []
for i in range(n) :
  a1,b1 = map(int,input().split())
  a.append(a1) ; b.append(b1)

#dp[i] = 体力iの敵を倒すのに必要な魔力の最低値
dp = [0,min(b)]

for i in range(2,a[b.index(min(b))]+1) :
  dp.append(min(b))

for i in range(a[b.index(min(b))]+1,h+1) :
  dp.append(10**10)
  for j in range (n) :
    if i-a[j] < 0 :
      continue
    dp[i] = min(dp[i],dp[i-a[j]]+b[j])

print(dp[h])

Submission status: Wrong Answer

Solution code:
import numpy as np
h, n = list(map(int, input().split()))
aa = []
bb = []
for k in range(n):
    a, b = list(map(int, input().split()))
    aa.append(a)
    bb.append(b)
aa = np.array(aa)
bb = np.array(bb)

def func1(x):
    x[x >= 0] = dp[x[x >= 0]]
    x[x < 0] = int(1e9) + 7
    return x

dp = np.array([0])

for k in range(1, h+1):
    t = func1(k-aa) + bb
    dp = np.append(dp, min(t))
while dp[-1] > int(1e9):
    k += 1
    t = func1(k-aa) + bb
    dp = np.append(dp, min(t))

print(dp[-1])

Submission status: Wrong Answer

Solution code:
hp,m=map(int,input().split())
l=[list(map(int,input().split())) for  i in range(m)]
dp=[10**7 for i in range(hp+1)]
dp[0]=0
for i in range(hp+1):
  for at,mp in l:
    dp[i]=min(dp[i],mp+(0 if i-at<0 else dp[i-at]))
print(dp[hp])

Submission status: Wrong Answer

Solution code:
a,s=map(int,input().split())
l=[list(map(int,input().split())) for  i in range(s)]
dp=[10**7 ]*(a+1)
dp[0]=0
for i in range(a+1):
  for g in range(s):
    dp[i]=min(dp[i],l[g][1]+(0 if i-l[g][0]<0 else dp[i-l[g][0]]))
print(dp[a])

Submission status: Wrong Answer

Solution code:
H,N = map(int,(input().split()))
dp = [10**9]*(H+1)
dp[0] = 0

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

for i in range(H+1):
    for j,k in A:
        next = min(H,i+j)
        dp[next] = min(dp[next],dp[i]+k)

print(dp[H])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from collections import defaultdict

def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    MAX = 10**7
    minCurrent = defaultdict(lambda :MAX)
    minCurrent[0] = 0
    currentPos = [0]
    heapq.heapify(currentPos)
    visited = set()
    while len(currentPos) > 0:
        cp = heapq.heappop(currentPos)
        if cp in visited:
            continue
        if cp > H:
            break
        visited.add(cp)
        cc = minCurrent[cp]
        for i in range(N):
            heapq.heappush(currentPos, cp + A[i])
            minCurrent[cp + A[i]] = min(minCurrent[cp + A[i]],cc+B[i])
    c = MAX
    for key in minCurrent:
        if key >=H:
            c = min(c,minCurrent[key])
    print(c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

dp = [1e7]*(H+max(A)+1)
dp[0] = 0
for h in range(0,H):
  for n in range(N):
    dp[h+A[n]] = min(dp[h+A[n]], dp[h]+B[n])
print(min(dp[H:]))

Submission status: Wrong Answer

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

import numpy as np
  


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

dp=[float('inf')]*(H+min(A)+1)
dp[0]=0
for h in range(1,H+1+min(A)):
  for i in range(N):
    if h-A[i]>=0:
      dp[h]=min(dp[h-A[i]]+B[i],dp[h])
print(min(dp[H:]))

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ab = []
for i in range(n):
    ab.append(list(map(int, input().split())))
    ab[i].append(ab[i][0] / ab[i][1])
# for i in ab:
#     print(i)
ans = 0
while True:
    max_effi = 0
    max_magic = []
    for i in range(n):
        if ab[i][0] > h:
            ab[i][0] = h
            ab[i][2] = ab[i][0] / ab[i][1]
    for i in range(n):
        if ab[i][2] > max_effi:
            max_effi = ab[i][2]
            max_magic = ab[i]
    ans += h // max_magic[0] * max_magic[1]
    # print(h, max_magic, h // max_magic[0], h % max_magic[0])
    h %= max_magic[0]
    if h == 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
import math

h, n = map(int, input().split())
a, b= [0]*(n+1), [0]*(n+1)
for i in range(n):
    aa, bb = map(int, input().split())
    a[i+1], b[i+1] = aa, bb

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

for mag_idx in range(1, n+1):
    for dam_idx in range(1, h+1):
        dp[mag_idx][dam_idx] = b[mag_idx] * math.ceil(dam_idx / a[mag_idx])
        val = dp[mag_idx-1][dam_idx]
        for i in range(dam_idx):
            val = min(val, dp[mag_idx-1][i] + dp[mag_idx][dam_idx-i])
        dp[mag_idx][dam_idx] = val
'''
for row in dp:
    print(row)
'''
print(dp[n][h])

Submission status: Wrong Answer

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

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort(key=lambda x: x[0])
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]), cost, data)

Submission status: Wrong Answer

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

for i in range(N):
    data.append([0, 0])
    a, b = map(int,input().split())
    data[i][0] = a
    data[i][1] = b
data.sort
cost = [float("inf")] * (H + data[-1][0])
cost[0] = 0
for i in range(1, H + data[-1][0]):
    for magic in data:
        if i < magic[0]:
            break
        if cost[i] > cost[i - magic[0]] + magic[1]:
            cost[i] = cost[i - magic[0]] + magic[1]
print(min(cost[H:]))

Submission status: Wrong Answer

Solution code:
#貪欲法で失敗したパターン

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

C = [0]*N
for i in range(N):
  a,b = map(int, input().split())
  cp = b/a
  C[i]=[a,b,b/a]

#print(C)
def battle(hp,magic):
  #print(hp,magic,end=' ')
  if hp==0:
    return magic
  for i,[a,b,cp] in enumerate(C):
    if a>hp:
      C[i][0]=hp
      C[i][2]=b/hp
  C.sort(key=lambda x:x[2])
  #print(*C[0])
  a,b,cp = C[0]
  num = hp//a
  hp -= a*num
  magic += b*num
  return battle(hp,magic)

magic = 0
ans = battle(H,magic)
print(ans)

Submission status: Wrong Answer

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

C = [0]*N
for i in range(N):
  a,b = map(int, input().split())
  cp = b/a
  C[i]=[a,b,b/a]

print(C)
def battle(hp,magic):
  print(hp,magic,end=' ')
  if hp==0:
    return magic
  for i,[a,b,cp] in enumerate(C):
    if a>hp:
      C[i][0]=hp
      C[i][2]=b/hp
  C.sort(key=lambda x:x[2])
  print(*C[0])
  a,b,cp = C[0]
  num = hp//a
  hp -= a*num
  magic += b*num
  return battle(hp,magic)

magic = 0
ans = battle(H,magic)
print(ans)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
magics = [tuple(map(int, input().split())) for _ in range(N)]
inf = 10 ** 7 + 1

"""
dp[h]: hの攻撃を与える際の、最小魔力消費量
"""
dp = [inf] * (H + 1 + 10**4)
dp[0] = 0

for h in range(H+1):
    for a, b in magics:
        dp[h + a] = min(dp[h] + b, dp[h + a])

print(min(dp[H:]))

Submission status: Wrong Answer

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

INF = int(1e18)
dp = [INF] * (H + 1)
dp[H] = 0;
for i in range(N):
    for j in range(H, -1, -1):
        dp[max(0, j - A[i][0])] = min(dp[max(0, j - A[i][0])], dp[j] + A[i][1])

ans = dp[0]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,N=map(int,input().split())
l=[1000000000]*(H+1)
l[0]=0
for i in range(N):
    A,B=map(int,input().split())
    for j in range(H):
        if j+A<=H and l[j]+B<l[j+A]:
            l[j+A]=l[j]+B
    t=1000000000
    for j in range(H,-1,-1):
        if l[j]>t:
            l[j]=t
        else:
            t=l[j]
print(l[-1])

Submission status: Wrong Answer

Solution code:
def main():

    H, N = map(int, input().split())
    dam, mp = [0] * N, [0] * N
    for i in range(N):
        dam[i], mp[i] = map(int, input().split())

    # dp[i magic][j damage] := min mp
    H_MAX = H + max(dam)
    dp = [[float('inf') for _ in range(H_MAX + 1)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(H_MAX + 1):
            if j - dam[i] >= 0:
                if dp[i + 1][j - dam[i]] == float('inf'):
                    if j == dam[i]:
                        dp[i + 1][j] = mp[i]
                    else:
                        dp[i + 1][j] = dp[i][j]
                else:
                    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - dam[i]] + mp[i])

    print(min(dp[N][H:]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():

    H, N = map(int, input().split())
    dam, mp = [0] * N, [0] * N
    for i in range(N):
        dam[i], mp[i] = map(int, input().split())

    # dp[i magic][j damage] := min mp
    dp = [[float('inf') for _ in range(H * 2)] for _ in range(N + 1)]
    for i in range(N):
        for j in range(H * 2):
            if j - dam[i] >= 0:
                if dp[i + 1][j - dam[i]] == float('inf'):
                    if j == dam[i]:
                        dp[i + 1][j] = mp[i]
                    else:
                        dp[i + 1][j] = dp[i][j]
                else:
                    dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - dam[i]] + mp[i])

    print(min(dp[N][H:]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)

  dp=[[inf]*(h+10**4+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(h+10**4):
      if j<w[i]:
        dp[i+1][j]=dp[i][j]
      else:
        dp[i+1][j]=min(dp[i][j],dp[i+1][j-w[i]]+v[i])
  ans=inf
  for i in range(n+1):
    for j in range(h,h+10**4):
      ans=min(ans,dp[i][j])

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,n=LI()
  w=[]
  v=[]
  for _ in range(n):
    _w,_v=LI()
    w.append(_w)
    v.append(_v)

  dp=[[0]*(h+1) for _ in range(n+1)]
  for i in range(n):
    for j in range(h):
      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])
  return dp[n][h]

# main()
print(main())

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
inf = 10**7

# i番目の魔法までを駆使して、体力xを倒す
@lru_cache(maxsize=None)
def f(i, k):
    a, b = ab[i]
    if i == -1:
        return inf
    if k <= 0:
        return 0
    if k >= a:
        return min(f(i-1, k), f(i-1, k-a) + b, f(i, k-a) + b)
    return min(f(i-1, k), b)


print(f(n-1, h))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,N = LMIIS()
    AB = XLMIIS(N)
    #最小消費量[価値]
    dp = [-1]*20000
    dp[0] = 0
    for i in range(H):
        if dp[i] == -1:
            continue
        for a,b in AB:
            if dp[i+a] == -1 or dp[i] + b < dp[i+a]:
                dp[i+a] = dp[i] + b

    for i in range(H,200000):
        if dp[i] != -1:
            print(dp[i])
            return



            




    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
INF = 1000000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

for i in range(1, h+maxA):
    for ab in AB*2:
        a, b = ab[0], ab[1]
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)

print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
INF = 1000000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA+1)]
dp[0] = 0

for i in range(1, h+maxA+1):
    for ab in AB:
        a, b = ab[0], ab[1]
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1000000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

for i in range(1, h+maxA):
    for ab in AB:
        a, b = ab[0], ab[1]
        if i-a >= 0:
            dp[i] = min(dp[i], dp[i-a] + b)

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1000000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

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

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
INF = 10000000

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

maxA = max(AB[:][0])

dp = [INF for i in range(h+maxA)]
dp[0] = 0

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

ans = min(dp[h:])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N=map(int,list(input().split(" ")))
magic=[]
power=[]
for i in range(N):
    A,B=map(int,list(input().split(" ")))
    magic+=[A]
    power+=[B]
dp=[[np.inf for i in range(2*H+1)] for j in range(N+1)]
for i in range(N+1):
    dp[i][0]=0
ma=[]
for j in range(1,2*H+1):
    for i in range(1,N+1):
        if j-magic[i-1]>=0:
            dp[i][j]=min(dp[i-1][j],dp[i][j-magic[i-1]]+power[i-1])
        else:
            dp[i][j]=dp[i-1][j]
print(min(dp[N][H:]))

Submission status: Wrong Answer

Solution code:
import numpy as np
H,N=map(int,list(input().split(" ")))
magic=[]
power=[]
for i in range(N):
    A,B=map(int,list(input().split(" ")))
    magic+=[A]*(H//A+1)
    power+=[B]*(H//A+1)
n=len(magic)
power=[0]+power
magic=[0]+magic
dp=[[np.inf for i in range(2*H+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
ma=[]
for j in range(1,2*H+1):
    for i in range(1,n+1):
        if j-magic[i]>=0:
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-magic[i]]+power[i])
        else:
            dp[i][j]=dp[i-1][j]
print(min(dp[n][H:]))

Submission status: Wrong Answer

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

inf = 1000000000
dp = [inf] * 20000
dp[0] = 0
for i in range(h + 1):
    for j in range(n):
        dp[i + a[j]] = min(dp[i + a[j]], dp[i] + b[j])

print(dp[h])

Submission status: Wrong Answer

Solution code:
import math

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

#print(a)
#print(b)
INF = int(1e10)
dp = [[INF] * (h+1) for i in range(n+1)]
for i in range(h+1):
    dp[0][i] = math.ceil(i / a[0]) * b[0]
for i in range(n):
    dp[i][0] = 0
for i in range(n):
    for j in range(h+1):
        if j < a[i]:
            dp[i+1][j] = min(-(-j / a[i]) * b[i], dp[i][j])
        else:
            dp[i+1][j] = min(-(-j/ a[i]) * b[i], dp[i][j], dp[i+1][j - a[i]] + b[i])
#print(dp)
print(dp[n][h])