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 itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
H, N = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
A_B = [list(map(int,input().split())) for _ in range(N)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# edges = [list(map(int,input().split())) for _ in range(N - 1)]
# tree = [[] for _ in range(N + 1)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0
# count = [0] * (N + 1)

# for i in range(Q):
#     p, x = map(int, input().split())
#     count[p] += x

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)


# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

max_a = max(a for a, b in A_B)

max_damege = H + max_a

dp = [0] * (max_damege + 1)

for i in range(max_damege + 1):
    dp[i] = min(dp[i-a]+b for a,b in A_B)

print(dp[H-1:])

print(min(dp[H-1:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[0]
b=[0]
width=2*10**4+7
dp=[[10**10 for i in range(width)] for j in range(n+1)]
dp[0][0]=0
dp[1][0]=0
for i in range(n):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
for i in range(1,n+1):
    for j in range(width):
        dp[i][j]=min(dp[i][j],dp[i-1][j])
        if(j+a[i]<=10):
            dp[i][j+a[i]]=min(dp[i][j+a[i]],dp[i][j]+b[i])
print(min(dp[n][h:]))

Submission status: Wrong Answer

Solution code:
h,n = map(int,input().split())
P = []
M = []
cospa = []

cost = 0

for i in range(n):
    p,m = map(int,input().split())  
    P.append(p)
    M.append(m)
    cospa.append((min(p,h))/m)
    


# main weapon
mw = cospa.index(max(cospa))

kai = (h // P[mw])
cost += M[mw] * kai
h %= P[mw]

print()

# low cost weapon
lw = M.index(min(M))

while h>P[lw]:
    
    for i in range(n):
        cospa[i] = (min(P[i],h))/M[i]

    # main weapon
    mw = cospa.index(min(cospa))
    
    kai = 1
    cost += M[mw] * kai
    h -= P[mw]
    
if h>0:
    # low cost weapon
    
    cost += M[lw]
    h -= P[lw] 
      
print(cost)

Submission status: Wrong Answer

Solution code:

h,n = map(int,input().split())
P = []
M = []
cospa = []

cost = 0

for i in range(n):
    p,m = map(int,input().split())  
    P.append(p)
    M.append(m)
    cospa.append((min(p,h))/m)
    


# main weapon
mw = cospa.index(max(cospa))

cost += M[mw] * (h // P[mw])
h %= P[mw]

# low cost weapon
lw = M.index(min(M))

while h>P[lw]:
    
    for i in range(n):
        cospa[i] = (min(P[i],h))/M[i]

    # main weapon
    mw = cospa.index(min(cospa))
    
    h %= P[mw]
    cost += M[mw] * (h // P[mw])
    
if h>0:
    # low cost weapon
    
    cost += M[lw]
    h %= P[lw] 
      
print(cost)

Submission status: Wrong Answer

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

x = 10**10
dp = [x]*(H+1)
dp[0] = 0

for a, b in zip(A, B):
    for i in range(a, H+1):
        dp[i] = min(dp[i-a]+b, dp[i])
    for i in range(H-1, -1, -1):
        dp[i] = min(dp[i+1], dp[i])

print(dp[H])

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
INF = float("inf")
dp0 = [INF]*(H+1)
dp1 = [INF]*(H+1)
dp0[0] = 0
for i in range(N):
    a,b = AB[i]
    dp1[H] = dp0[H]
    for h in range(H-1, -1, -1):
        dp1[h] = min(dp0[h], dp1[h+1])
    assert dp1[0] == 0
    for h in range(H+1):
        if h-a >= 0:
            dp1[h] = min(dp1[h], dp1[h-a]+b)
    t = dp1
    dp1 = dp0
    dp0 = t
print(dp0[H])

Submission status: Wrong Answer

Solution code:
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for (A, B) in AB:
    for j in range(H+1):
        if dp[j] >= INF:
            break
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])

Submission status: Wrong Answer

Solution code:
import numpy as np
INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = np.full((N+1, W+1), INF, dtype = np.int64)
dp[0][0] = 0
for i, (A, B) in enumerate(AB):
    dp[i+1] = np.minimum(dp[i+1], dp[i])
    dp[i+1][A:] = np.minimum(dp[i+1][A:], dp[i+1][:-A] + B)
print(np.min(dp[N][H:W+1]))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
M = dict(iter([tuple(map(int, input().split())) for i in range(N)]))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for i in range(1, H + 1):
    dp[i] = min(dp[max(0, i - a)] + b for a, b in M.items())

print(dp[H])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
M = dict(iter([tuple(map(int, input().split())) for i in range(N)]))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for a, b in M.items():
    for i in range(H + 1):
        dp[i] = min(dp[i], dp[max(0, i - a)] + b)

print(dp[H])

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
M = dict(iter([tuple(map(int, input().split())) for i in range(N)]))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for a, b in M.items():
    for i in range(H + 1):
        dp[i] = min(dp[i], dp[max(0, i - a)] + b)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
M = dict(iter([tuple(map(int, input().split())) for i in range(N)]))
dp = [float('inf') for i in range(H + 1)]
dp[0] = 0

for i in range(H + 1):
    for a, b in M.items():
        dp[i] = min(dp[i], dp[max(0, i - a)] + b)

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)]
ab.sort()

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    pc=0
    for a,b in ab:
        if a+i>H:
            a=H-i
            pc+=1
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
    for _ in range(pc):
        ab.pop()
    i+=1

print(ans[H])

Submission status: Wrong Answer

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

ans=[10**9]*(H+1)
ans[0]=0
i=0
while i<=H:
    pc=0
    for a,b in ab:
        if a+i>H:
            a=H-i
            pc+=1
        if ans[i+a]>ans[i]+b:
            ans[i+a]=ans[i]+b
        for _ in range(pc):
            ab.pop()
    i+=1

print(ans[H])

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
L=[]
max_b=0
for i in range(N):
    a,b=map(int,input().split())
    max_b=max(max_b,b)
    L.append((a/b,a,b))
L.sort(reverse=True)
l,r=0,max_b*H+1
while not l+1==r:
    x=(l+r)//2
    tmp=0
    k=x
    for _,a,b in L:
        tmp+=a*(k//b)
        k%=b
        if tmp>=H:
            break
    if tmp>=H:
        r=x
    else:
        l=x
print(r)

Submission status: Wrong Answer

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

magics = [None]


class Magic:
    def __init__(self, attack, cost):
        self.attack = attack
        self.cost = cost


maxA = 0
for i in range(n):
    attack, cost = [int(i) for i in input().split()]
    maxA = max(maxA, attack)
    magics.append(Magic(attack, cost))

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

for i in range(n + 1):
    for j in range(h + maxA):
        if j == 0:
            dp[i][j] = 0
        elif i == 0:
            continue
        elif j - magics[i].attack >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i][j - magics[i].attack] + magics[i].cost)

print(min(dp[-1][h:]))

Submission status: Wrong Answer

Solution code:
H, N = [int(s) for s in input().split()]
mahou = [[int(a) for a in input().split()] for _ in range(N)]
mahou = sorted(mahou, key=lambda x: x[1])

DP = [10 ** 9] * (H + 1)
DP[0] = 0

for i in range(1, H+1):
    for j in range(N):
        if i >= mahou[j][0]:
            DP[i] = min(DP[i], DP[i - mahou[j][0]] + mahou[j][1])

if DP[H] < 10 ** 9:
    print(DP[H])
    exit()


for i in range(H, 0, -1):
    if DP[i] < 10 ** 9:
        for j in range(N):
            if H - i <= mahou[j][0]:
                print(DP[i] + mahou[j][1])
                exit()

for j in range(N):
    if H <= mahou[j][0]:
        print(mahou[j][1])

Submission status: Wrong Answer

Solution code:
H, N = [int(s) for s in input().split()]
mahou = [[int(a) for a in input().split()] for _ in range(N)]
mahou = sorted(mahou, key=lambda x: x[1])

DP = [10 ** 9] * (H + 1)
DP[0] = 0

for i in range(1, H+1):
    for j in range(N):
        if i >= mahou[j][0]:
            DP[i] = min(DP[i], DP[i - mahou[j][0]] + mahou[j][1])

if DP[H] < 10 ** 9:
    print(DP[H])
    exit()


for i in range(H, 0, -1):
    if DP[i] < 10 ** 9:
        for j in range(N):
            if H - i <= mahou[j][0]:
                print(DP[i] + mahou[j][1])
                exit()

for j in range(N):
    if H - i <= mahou[j][0]:
        print(mahou[j][1])

Submission status: Wrong Answer

Solution code:

H, N = [int(s) for s in input().split()]
mahou = [[int(a) for a in input().split()] for _ in range(N)]
mahou = sorted(mahou, key=lambda x: x[1])

DP = [10 ** 9] * (H + 1)
DP[0] = 0

for i in range(1, H+1):
    for j in range(N):
        if i >= mahou[j][0]:
            DP[i] = min(DP[i], DP[i - mahou[j][0]] + mahou[j][1])

if DP[H] < 10 ** 9:
    print(DP[H])
    exit()


for i in range(H, 0, -1):
    if DP[i] < 10 ** 9:
        for j in range(N):
            if H - i <= mahou[j][0]:
                print(DP[i] + mahou[j][1])
                exit()

for j in range(N):
    if H - i <= mahou[j][0]:
        print(DP[i] + mahou[j][1])

Submission status: Wrong Answer

Solution code:
H, N = [int(s) for s in input().split()]
mahou = [[int(a) for a in input().split()] for _ in range(N)]
mahou = sorted(mahou, key=lambda x: x[1])

DP = [10 ** 9] * (H + 1)
DP[0] = 0

for i in range(1, H+1):
    for j in range(N):
        if i >= mahou[j][0]:
            DP[i] = min(DP[i], DP[i - mahou[j][0]] + mahou[j][1])

if DP[H] < 10 ** 9:
    print(DP[H])
    exit()


for i in range(H, 0, -1):
    if DP[i] < 10 ** 9:
        for j in range(N):
            if H - i <= mahou[j][0]:
                print(DP[i] + mahou[j][1])
                exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)

h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))

ld = [(k,v) for k, v in d.items()]
len_d = len(ld)
memo = {}
def f(index, current, damage):
  if memo.get(current, 0) > damage:
    return
  memo[max(h, current)] = damage
  for i in range(index, len_d):
    if damage+ld[i][1] <= h:
      f(i, current+ld[i][0], damage+ld[i][1])

f(0, 0, 0)
i = 0
while memo.get(i, 0) < h:
  i += 1
print(i)

Submission status: Wrong Answer

Solution code:
h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))
#print(d)
best = 0
best_k = 0
best_v = 0
for k in sorted(d):
  v = d[k]
  if best < v / k:
    best = v / k
    best_k = k
    best_v = v
temp = 0
while h >= best_v:
  h -= best_v
  temp += best_k
#print(h, temp, best_k, best, best * best_k)
ans = 9999999999999999999999
memo = {}
sorted_d = sorted(d)[::-1]
def f(current, damage):
  #print(current, damage, h)
  global ans
  if damage and memo.get(current, 0) >= damage:
    return memo.get(current, 0)
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
    return ans
  hoge = 0
  for k in sorted_d:
    hoge = max(hoge, f(current+k, damage+d[k]))
  return hoge
f(0, 0)
#print(temp, (ans if ans != 9999999999999999999999 else 0))
print(temp + (ans if ans != 9999999999999999999999 else 0))

Submission status: Wrong Answer

Solution code:
h, n = list(map(int, input().split(' ')))
d ={}
for i in range(n):
  a, b = list(map(int, input().split(' ')))
  d[b] = max(a, d.get(b, 0))
#print(d)
best = 0
best_k = 0
best_v = 0
for k in sorted(d):
  v = d[k]
  if best < v / k:
    best = v / k
    best_k = k
    best_v = v
temp = 0
while h/10 >= best_v:
  h -= best_v
  temp += best_k
#print(h, temp, best_k, best, best * best_k)
ans = 9999999999999999999999
memo = {}
sorted_d = sorted(d)[::-1]
def f(current, damage):
  #print(current, damage, h)
  global ans
  if damage and memo.get(current, 0) >= damage:
    return memo.get(current, 0)
  memo[current] = damage
  if damage >= h:
    ans = min(ans, current)
    return ans
  hoge = 0
  for k in sorted_d:
    hoge = max(hoge, f(current+k, damage+d[k]))
  return hoge
f(0, 0)
print(temp, (ans if ans != 9999999999999999999999 else 0))
print(temp + (ans if ans != 9999999999999999999999 else 0))

Submission status: Wrong Answer

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

waza=[None]

class Waza:
    def __init__(self,attack,power):
        self.attack=attack
        self.power=power

maxA=0
for i in range(n):
    a,b=[int(i) for i in input().split()]
    maxA=max(maxA,a)
    waza.append(Waza(a,b))


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

for i in range(n+1):
    for j in range(h+maxA):
        if j==0:
            dp[i][j]=0
        elif i==0:
            pass
        elif j-waza[i].attack>=0:
            dp[i][j]=min(dp[i-1][j],dp[i][j-waza[i].attack]+waza[i].power)

print(min(dp[-1][h:]))

Submission status: Wrong Answer

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

waza=[None]

class Waza:
    def __init__(self,attack,power):
        self.attack=attack
        self.power=power

maxA=0
for i in range(n):
    a,b=[int(i) for i in input().split()]
    maxA=max(maxA,a)
    waza.append(Waza(a,b))


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

for i in range(n+1):
    for j in range(h+maxA):
        if j==0:
            dp[i][j]=0
        elif i==0:
            pass
        elif j-waza[i].attack>=0:
            dp[i][j]=min(dp[i-1][j],dp[i][j-waza[i].attack]+waza[i].power)

print(min(dp[-1][h:]))

Submission status: Wrong Answer

Solution code:
import heapq

class Magic:
    def __init__(self,attack,power):
        self.attack=attack
        self.power=power
        self.effi=None

    def set_effi(self,h):
        self.effi=min(h,self.attack)/self.power

    def __eq__(self,other):
        if self.effi==other.effi:
            return True
        else:
            return False

    def __ge__(self,other):
        if self.effi<=other.effi:
            return True
        else:
            return False

    def __gt__(self,other):
        if self.effi<other.effi:
            return True
        else:
            return False

    def __le__(self,other):
        if self.effi>=other.effi:
            return True
        else:
            return False

    def __lt__(self,other):
        if self.effi>other.effi:
            return True
        else:
            return False

magic_list=[]
h,n=[int(i) for i in input().split()]

for i in range(n):
    a,b=[int(i) for i in input().split()]
    magic=Magic(a,b)
    magic_list.append(magic)

def set_effi(heapq,h):
    for i in heapq:
        i.set_effi(h)

set_effi(magic_list,h)
heapq.heapify(magic_list)


ans=0
while True:
    ideal_magic=magic_list[0]
    ans+=ideal_magic.power
    h=max(0,(h-ideal_magic.attack))
    # for i in magic_list:
    #     print(i.effi)

    set_effi(magic_list,h)
    magic_list.sort()
    if h==0:
        break


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl
import math


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    h, n = MI()
    a = []
    b = []
    mahou = []
    for i in range(n):
        _a, _b = MI()
        a.append(_a)
        b.append(_b)
        mahou.append([_a, _b])

    max_a = max(a)

    mahou.sort()
    for i in range(n):
        a[i] = mahou[i][0]
        b[i] = mahou[i][1]

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

    for j in range(h+1 + max_a):
        dp[0][j] = math.ceil(j / a[0]) * b[0]

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

            dp[i][j] = min(prev + b[i], dp[i-1][j])

    print(min(dp[-1][h:h+max_a]))


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl
import math


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    h, n = MI()
    a = []
    b = []
    mahou = []
    for i in range(n):
        _a, _b = MI()
        a.append(_a)
        b.append(_b)
        mahou.append([_a, _b])

    mahou.sort()
    for i in range(n):
        a[i] = mahou[i][0]
        b[i] = mahou[i][1]

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

    for j in range(h+1):
        dp[0][j] = math.ceil(j / a[0]) * b[0]

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

            dp[i][j] = min(prev + b[i], dp[i-1][j])

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


main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl
import math


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    h, n = MI()
    a = []
    b = []
    for i in range(n):
        _a, _b = MI()
        a.append(_a)
        b.append(_b)

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

    for j in range(h+1):
        dp[0][j] = math.ceil(j / a[0]) * b[0]

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

            dp[i][j] = min(prev + b[i], dp[i-1][j])

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


main()

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = [0] * N
damage = [0] * N
for i in range(N):
  AB[i] = list(map(int, input().split()))
  damage[i] = AB[i][0]
  
x = min(AB, key = lambda x:x[1])
x = x[1]
  
DP = [10 ** 10] * (H + 1)#ダメージを与える最小魔力
DP[0] = 0

for i in range(1, H + 1):
  for j in range(i):
    if j in damage:
      p = damage.index(j)
      DP[i] = min(DP[i], DP[i - j] + AB[p][1])
  if DP[i] == 10 ** 10:
    DP[i] = x
  
print(DP[H])

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)

a_max = max(a)
dp = [0]*(h+a_max)

for i in range(h+a_max):
    best = 10**6
    for j in range(n):
        best = min(dp[i-a[j]] + b[j], best)
    dp[i] = best

print(min(dp[h-1:]))

Submission status: Wrong Answer

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

A, B = [0]*N, [0]*N

maxDamage = H + max(A)

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


dp = [[float("inf") for _ in range(maxDamage+1)] for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(maxDamage+1):

        if j < A[i]:
            dp[i+1][j] = dp[i][j]

        else:
            res1 = dp[i][j]
            res2 = dp[i+1][j - A[i]] + B[i]

            dp[i+1][j] = min(res1, res2)
            # pprint.pprint(dp)
# pprint.pprint(dp)
for i in range(H, maxDamage+1):

    if dp[N][i] < float("inf"):
        print(dp[N][i])
        exit()

Submission status: Wrong Answer

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

A, B = [0]*N, [0]*N

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

maxCost = sum(B)

dp = [[0 for _ in range(maxCost+1)] for _ in range(N+1)]

for i in range(N):
    for j in range(maxCost+1):

        if A[i] > j:
            dp[i+1][j] = dp[i][j]
        else:
            res1 = dp[i][j]
            res2 = dp[i+1][j - B[i]] + A[i]
            dp[i+1][j] = max(res1, res2)

# import pprint
# pprint.pprint(dp)
for i in range(maxCost+1):

    if dp[N][i] >= H:
        print(i)
        exit()

Submission status: Wrong Answer

Solution code:
import numpy as np
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
while True:
  dp.append(np.inf)
  for i in range(N):
    if A[i]<=h:
      dp[-1]=min(dp[-1-A[i]] + B[i], dp[-1])
  if h>=H and dp[-1]!=np.inf:
    break
  h+=1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np
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
while True:
  dp.append(np.inf)
  for i in range(N):
    if A[i]<=h:
      dp[h]=min(dp[h-A[i]] + B[i], dp[h])
  if h>=H and dp[h]!=np.inf:
    break
  h+=1
print(dp[-1])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a_=0
magic=[]
for i in range(n):
  a,b=map(int,input().split())
  a_=max(a,a_)
  c=[a,b]
  magic.append(c)
dp=[10**7+1]*(h+a_+1)
dp[0]=0
for i in range(n):
  a,b=magic[i]
  for j in range(len(dp)):
    u=1
    while j+u*a<=h+a_:
      dp[j+u*a]=min(dp[j+u*a],dp[j]+u*b)
      u+=1
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a_=0
magic=[]
for i in range(n):
  a,b=map(int,input().split())
  a_=max(a,a_)
  c=[a,b]
  magic.append(c)
dp=[10**7+1]*(h+a_+1)
dp[0]=0
for i in range(n):
  a,b=magic[i]
  for j in range(len(dp)):
    if j+a<=h+a_:
      dp[j+a]=min(dp[j+a],dp[j]+b)
print(min(dp[h:]))

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)

ans = 0
while h > 0:
    a_best, b_best, c_best = 0, 0, 0
    for i in range(n):
        if a[i] > h:
            a[i] = h
        if a[i]/b[i] > c_best:
            a_best, b_best, c_best = a[i], b[i], a[i]/b[i]

    h -= a_best
    ans += b_best
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

for _ in range(N):
  a,b = map(int, input().split())
  ABs.append((a,b))
  
memo = [[sys.maxsize]*(H+1) for _ in range(N+1)]
memo[0][H] = 0

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

Submission status: Wrong Answer

Solution code:
(h,n),*c=[[*map(int,i.split())]for i in open(0)]
dp=[10**9]*(2*10**4+1)
c.sort()
dp[0]=0
for i in range(h):
    if dp[i]==10**9:break
    for a,b in c:
        if i+a<=2*10**4:
            dp[i+a]=min(dp[i+a],dp[i]+b)
        else:break    
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []
def solve(start, power, point, maryoku):
  if start == H:
    print(point)
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)
for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])
print(min(anskouho))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

for k in range(N):
  magic[k] = list(map(int, input().split()))
  magic[k].append(magic[k][0]/magic[k][1])

magic.sort(key = lambda x: x[2], reverse=True)
ans = [0 for _ in range(H+1)]
visited = [0]
anskouho = []
def solve(start, power, point, maryoku):
  if start == H:
    print(point)
    exit()
  elif start > H:
    anskouho.append(point)
    visited.sort(reverse=True)
    return 0
  elif ans[start] != 0:
    visited.sort(reverse=True)
    return 0
  else:
    visited.append(start)
    ans[start] = point
    solve(start+power, power, point+maryoku, maryoku)
for k in range(N):
  for item in visited:
    solve(item+magic[k][0], magic[k][0], ans[item] + magic[k][1], magic[k][1])
print(min(anskouho))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
ans=0
magic=[]
al=[]
bl=[]
for i in range(n):
  a,b=map(int,input().split())
  magic.append([a,b])
  al.append(a)
  bl.append(b)
amx=max(al)
bmn=min(bl)
dp=[-1]*(h+amx+1)
dp[0]=0
for i in range(1,h+amx+1):
  mn=9999999
  for j in magic:
    mp=j[1]
    at=j[0]
    if at>i:
      cst=mp
    else:
      cst=dp[i-at]+mp
    if cst<mn:
      mn=cst
  dp[i]=mn
  
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
ans=0
magic=[]
al=[]
bl=[]
for i in range(n):
  a,b=map(int,input().split())
  magic.append([a,b])
  al.append(a)
  bl.append(b)
amx=max(al)
bmn=min(bl)
dp=[-1]*(h+amx+1)
dp[0]=0
for i in range(1,h+amx+1):
  mn=9999999
  for j in magic:
    mp=j[1]
    at=j[0]
    if at>i:
      continue
    cst=dp[i-at]+mp
    if cst<mn:
      mn=cst
  if mn==9999999:
    mn=bmn
  dp[i]=mn
  
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
ans=0
magic=[]
al=[]
bl=[]
for i in range(n):
  a,b=map(int,input().split())
  magic.append([a,b])
  al.append(a)
  bl.append(b)
amx=max(al)
bmn=min(bl)
dp=[-1]*(h+amx+1)
dp[0]=0
for i in range(1,h+amx+1):
  mn=9999999
  for j in magic:
    mp=j[1]
    at=j[0]
    if at>i:
      continue
    cst=dp[i-at]+mp
    if cst<mn:
      mn=cst
  if mn==9999999:
    mn=bmn
  dp[i]=mn
  
print(min(dp[h:]))

Submission status: Wrong Answer

Solution code:
def chmin(dp, i, *x):
  dp[i] = min(dp[i], *x)
INF = float("inf")

# dp[i] := min 消耗する魔力 to H -= i
h, n = map(int, input().split())
dp = [INF]*-~h
for _ in [None]*n:
  a, b = map(int, input().split())
  for j in range(h + 1):
    chmin(dp, min(j + a, h), dp[j] + b)
print(dp[h])

Submission status: Wrong Answer

Solution code:
ATK = 0
MP = 1
EF = 2

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

gm = magics[0]  # great magic
for m in magics:
  if gm[EF] < m[EF]:
    gm = m

mp = (H // gm[ATK]) * gm[MP]
H = H % gm[ATK]

# totyuu

Submission status: Wrong Answer

Solution code:
INF = 1 << 60

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

MAX = h - 1 + max(a)
dp = [[INF for j in range(MAX)] for i in range(n)]
dp[0][0] = 0
if 0 <= a[0] < MAX:
    dp[0][a[0]] = b[0]
for j in range(MAX):
    if 0 <= j - a[0] < MAX:
        dp[0][j] = min(dp[0][j], dp[0][j - a[0]] + b[0])
for i in range(1, n):
    for j in range(MAX):
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if 0 <= j - a[i] < MAX:
            dp[i][j] = min(dp[i][j], dp[i][j - a[i]] + b[i])
ans = INF
for j in range(h, MAX):
    ans = min(ans, dp[-1][j])
print(ans)

Submission status: Wrong Answer

Solution code:
INF = 1 << 60

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

dp = [[INF for j in range(h * 2)] for i in range(n)]
dp[0][0] = 0
if 0 <= a[0] < h * 2:
    dp[0][a[0]] = b[0]
for j in range(h + 2):
    if 0 <= j - a[0] < h * 2:
        dp[0][j] = min(dp[0][j], dp[0][j - a[0]] + b[0])
for i in range(1, n):
    for j in range(h + 2):
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if 0 <= j - a[i] < h * 2:
            dp[i][j] = min(dp[i][j], dp[i][j - a[i]] + b[i])
ans = INF
for j in range(h, h * 2):
    ans = min(ans, dp[-1][j])
print(ans)