Problem:


Score : 500 points

Problem Statement

Ibis is fighting with a monster.

The health of the monster is H.

Ibis can cast N kinds of spells. Casting the i-th spell decreases the monster's health by A_i, at the cost of B_i Magic Points.

The same spell can be cast multiple times. There is no way other than spells to decrease the monster's health.

Ibis wins when the health of the monster becomes 0 or below.

Find the minimum total Magic Points that have to be consumed before winning.

Constraints

1 \leq H \leq 10^4

1 \leq N \leq 10^3

1 \leq A_i \leq 10^4

1 \leq B_i \leq 10^4

All values in input are integers.

Input

Input is given from Standard Input in the following format:

H N
A_1 B_1
:
A_N B_N

Output

Print the minimum total Magic Points that have to be consumed before winning.

Sample Input 1

9 3
8 3
4 2
2 1

Sample Output 1

4

First, let us cast the first spell to decrease the monster's health by 8, at the cost of 3 Magic Points. The monster's health is now 1.

Then, cast the third spell to decrease the monster's health by 2, at the cost of 1 Magic Point. The monster's health is now -1.

In this way, we can win at the total cost of 4 Magic Points.

Sample Input 2

100 6
1 1
2 3
3 9
4 27
5 81
6 243

Sample Output 2

100

It is optimal to cast the first spell 100 times.

Sample Input 3

9999 10
540 7550
691 9680
700 9790
510 7150
415 5818
551 7712
587 8227
619 8671
588 8228
176 2461

Sample Output 3

139815



Sample input:
9 3
8 3
4 2
2 1


Sample output:
4

Submission status: Wrong Answer

Solution code:
def solve(H, N, spell_damages, spell_costs):
  spell_efficiencies = sorted(
    [(spell_damages[i] / spell_costs[i], i) for i in range(N)],
    key=lambda x: (x[0], spell_damages[x[1]], spell_costs[x[1]], -x[1]),
    reverse=True
  )

  total_costs = 0
  i = 0
  while i < N and H > 0:
    idx = spell_efficiencies[i][1]
    if spell_damages[idx] > H:
      i += 1
    else:
      #print("Used: {}, damage: {}, cost: {}".format(idx, spell_damages[idx], spell_costs[idx]))
      H -= spell_damages[idx]
      total_costs += spell_costs[idx]

  if H > 0 and i > 0:
    idx = spell_efficiencies[i - 1][1]
    #print("Used: {}, damage: {}, cost: {}".format(idx, spell_damages[idx],spell_costs[idx]))
    total_costs += spell_costs[idx]

  print(total_costs)


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

spell_damages, spell_costs = [], []
H, N = iln()
for i in range(N):
  a,b = iln()
  spell_damages.append(a)
  spell_costs.append(b)
  
solve(H, N, spell_damages, spell_costs)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	H,N = inputMap()
	magia_mp = []
	hp = []
	magia_hp = []
	for i in range(N):
		A,B = inputMap()
		hp.append(A)
		magia_hp.append((A,B))
		magia_mp.append((B,A))

	magia_hp.sort()
	hp.sort()
	magia_mp.sort()

	B,A = magia_mp[0]
	tmp = -(-H // A)
	ans1 = B*tmp

	ans2 = 0
	while True:
		if H <= 0:
			break

		tmp = bisect_right(hp, H)
		if tmp == len(hp):
			tmp -= 1
		#print(tmp)
		A,B = magia_hp[tmp]

		H -= A
		ans2 += B

	print(min(ans1,ans2))


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

cost_to_damage = {v: k for k, v in damage_to_cost.items()}
cost_performances = {k: k / v for k, v in damage_to_cost.items()}


lowest_cost = min(damage_to_cost.values())
lowest_cost_damage = cost_to_damage[lowest_cost]

high_damage, _ = max(cost_performances.items(), key=lambda x: x[1])
high_cost = damage_to_cost[high_damage]

used_mp = 0
while H > 0:
    if H <= lowest_cost:
        used_mp += lowest_cost
        H -= lowest_cost
    else:
        used_mp += high_cost
        H -= high_damage

print(used_mp)

Submission status: Wrong Answer

Solution code:
def main():
    import math
    from operator import itemgetter
    H,N = map(int,input().split())
    AB = [list(map(int,input().split())) for _ in range(N)]
    ans = 0
    cost = [AB[i][0]/AB[i][1] for i in range(N)]
    flag = False
    while True:
        if flag:
            break
        cp = AB[cost.index(max(cost))]
        ans += cp[1]*math.floor(H/cp[0])
        H -= (math.floor(H/cp[0])*cp[0])
        sab = sorted(AB,key=itemgetter(1))
        for i in range(N):
            if H - sab[i][0] <= 0:
                ans += sab[i][1]
                flag = True
                break
        AB[cost.index(max(cost))] = [0,1]
        cost[cost.index(max(cost))] = 0
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
d=[list(map(int,input().split()))for i in range(n)]
p=[float("INF")]*max(h+1,2*d[-1][0]+1)
p[0]=0
s=max(h+1,2*d[-1][0]+1)
for i in range(n):
    a,b=d[i][0],d[i][1]
    for j in range(a,h+1):
        if p[j]>p[j-a]+b:
            p[j]=p[j-a]+b
print(min(p[h:]))

Submission status: Wrong Answer

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

dp = [[10 ** 9] * (H + 1) for _ in range(N + 1)]
dp[0][0] = 0
X.sort(key=lambda x: x[-1])

for i, (a, b) in enumerate(X):
    for j in range(H + 1):
        if j + a < H:
            dp[i + 1][j + a] = min(dp[i][j + a], dp[i][j] + b, dp[i + 1][j] + b)
        else:
            dp[i + 1][-1] = min(dp[i][-1], dp[i + 1][-1], dp[i][j] + b, dp[i + 1][j] + b)

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

Submission status: Wrong Answer

Solution code:
import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for _ in range(N)])

INF = 10**7 + 2
dp = np.full(2 * 10**4 + 2, INF, np.int32)
dp[0] = 0

for a, b in AB:
    for _ in range(H // a):
        prev = dp.copy()
        np.minimum(dp[a:], prev[:-a] + b, out=dp[a:])

print(np.min(dp[H:]))

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
t = list()
D = 0
num = 0
for i in range(N):
    A,B = map(int,input().split())
    C = A/B
    if D <= C:
        D = C
        num = i
    t.append([A,B])
    
p = sorted(t,key = lambda x:x[1])
if H // t[num][0] < 1:
    for i in range(N):
        if p[i][0] >= H:
            print(p[i][1])
            break
        
elif H % t[num][0] == 0:
    print(H // t[num][0] * t[num][1])
    
else:
    remain = H % t[num][0]
    for i in range(N):
        if p[i][0] >= remain:
            print(H // t[num][0] * t[num][1] + p[i][1])
            break

Submission status: Wrong Answer

Solution code:
#coding:utf-8

def main():
    h, n = map(int, input().split())
    ab = []
    for _ in range(n):
        ab.append(list(map(int, input().split())))
    
    inf = 1000000
    # indexがモンスターに与えたダメージで、中身がトキのダメージ
    damages = [inf for _ in range(100000)]
    damages[0] = 0
    for i in range(h):
        if damages[i] == inf:
            continue
        for j in range(n):
            new_damage = ab[j][0]
            if damages[i + new_damage] > damages[i] + ab[j][1]:
                damages[i + new_damage] = damages[i] + ab[j][1]
    
    # k = h
    # while damages[k] == inf:
    #     k += 1
    #     print(damages[k])
    print(min(damages[h:]))
main()

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    H, N = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [10**7+1] * (H+1)
    dp[0] = 0
    for a, b in AB:
        for i in range(H+1):
            if i - a >= 0:
                dp[i] = min(dp[i], dp[i-a] + b)
            else:
                dp[i] = min(dp[i], b)

    print(dp[H])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ablis = []
for i in range(n):
    a, b = map(int, input().split())
    ablis.append([a/b, a, b])
ablis.sort(reverse=True)
score = 0
"""score = (h // ablis[0][1]) * ablis[0][2]"""
"""h = h - (h // ablis[0][1]) * ablis[0][1]"""
while h > 0:
    for i in range(n):
        if ablis[i][1] > h:
            ablis[i][0] = (h/ablis[i][2])
    ablis.sort(reverse=True)
    h = h - ablis[0][1]
    score += ablis[0][2]
print(score)

Submission status: Wrong Answer

Solution code:

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

magics = []
for _ in range(N):
    magics.append(list(map(int, input().split())))

# 魔法にダメージ効率を追加
for magic in magics:
    magic.append(magic[0]/magic[1])


# 魔法を効率順にソート
magics.sort(key=lambda x: x[2], reverse=True)

ans = 0

kaisu = H // magics[0][0]
nokori = H % magics[0][0]

ans += kaisu * magics[0][1]

if nokori > 0:
    # 残りライフ以上のダメージを与えられる中で最小コストの魔法を使う
    lc = float('inf')
    for magic in magics:
        if magic[0] >= nokori:
            lc = min(lc, magic[1])

    ans += lc

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

Submission status: Wrong Answer

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

dg = 10**5

ba = []
for _ in [0]*n:
    a,b = map(int,input().split())
    if a >= h:
        a = h
    ba.append(b*dg+a)
ba.sort()

d = [0]*(h+1)

a,b = ba[0]%dg,ba[0]//dg
d[0] = 0
for i in range(1,h+1):
    if i%a == 0:
        d[i] = (i//a)*b
    else:
        d[i] = (i//a+1)*b


for i in range(1,n):
    a,b = ba[i]%dg,ba[i]//dg
    if d[a] >= b:
        for j in range(a,h+1):
            if d[j] > d[j-a]+b:
                d[j] = d[j-a]+b

print(d[-1])

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

INF = 1<<60
dp = [[INF]*(N+1) for _ in range(H+1)]
for i in range(N+1):
    dp[0][i] = 0

tmpj = 0
for j in range(H+1): 
    for i in range(N):
        if (j>=A[i]):
            tmp = dp[j-A[i]][i+1]+B[i]
            if tmp<=dp[j][i]:
                dp[j][i+1] = tmp
                tmpj = j        
            else:
                dp[j][i+1] = dp[j][i]
        else:
            dp[j][i+1] = dp[j][i]

ans = INF
if tmpj<H:
    tmp = dp[tmpj][N]
    for i in range(N):
        if tmpj+A[i]>=H:
            ans = min(ans,tmp+B[i])
    
else:
    ans = dp[H][N]

print(ans)

Submission status: Wrong Answer

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
ablis = []
for i in range(n):
    a, b = map(int, input().split())
    ablis.append([a/b, a, b])
ablis.sort(reverse=True)
score = (h // ablis[0][1]) * ablis[0][2]
h = h - (h // ablis[0][1]) * ablis[0][1]
while h > 0:
    for i in range(n):
        if ablis[i][1] > h:
            ablis[i][0] = (h/ablis[i][2])
    ablis.sort(reverse=True)
    h = h - ablis[0][1]
    score += ablis[0][2]
print(score)

Submission status: Wrong Answer

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

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

M = H+1

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

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

Submission status: Wrong Answer

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

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

for i, (a, b) in enumerate(X):
    for j in range(H + 1):
        if j + a < H:
            dp[i + 1][j + a] = min(dp[i][j + a], dp[i][j] + b, dp[i + 1][j] + b)
        else:
            dp[i + 1][-1] = min(dp[i][-1], dp[i + 1][-1], dp[i][j] + b, dp[i + 1][j] + b)

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

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h+1 + 10**4)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h+1+10**4):
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = min(dp[i][j], b)
print(dp[-1][h-1])

Submission status: Wrong Answer

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

def l():
    a, b = map(int, input().split())
    return P(a, b)

class P:
    def __init__(self, f, s):
        self.f = f
        self.s = s

    def __lt__(self, other):
        return self.s * other.f < other.s * self.f

AB = [l() for _ in range(N)]
AB = sorted(AB)

dp = [INF] * (H + 1)
dp[0] = 0
for i in range(H):
    for p in AB:
        dp[i + 1] = min(dp[i + 1], dp[i] + p.s)
        if i + p.f > H:
            continue
        dp[i + p.f] = min(dp[i + p.f], dp[i] + p.s)

print(dp[H])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h+1 + 10**4)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h+1+10**4):
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = min(dp[i+1][j], b)
print(dp[-1][h-1])

Submission status: Wrong Answer

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

    dp = [float("inf")]*(H + 10010)
    mx = 10**8
    for a,b in AB:
        dp[a] = min(dp[a],b)
    for i in range(1,H + 1):
        if dp[i] > mx:
            continue
        for a,b in AB:
            if i + a > H:
                dp[H] = min(dp[H],dp[i] + b)
            else:
                dp[i + a] = min(dp[i + a],dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, n = map(int, input().split())
    m = [tuple(map(int, input().split())) for _ in range(n)]

    a, b = m[0]
    dp = [[10**18] * (h + 1) for _ in range(n)]
    dp[0] = [((i + a - 1) // a) * b for i in range(h + 1)]
    for i in range(1, n):
        a, b = m[i]
        for j in range(h + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= a:
                dp[i][j] = min(dp[i][j], b + dp[i][max(0, j - a)])

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


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
# mahous = [(a, b) for a, b in list(map(int, input().split()))]

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

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

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

print(dp[H])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, n = map(int, input().split())
    m = [tuple(map(int, input().split())) for _ in range(n)]

    a, b = m[0]
    dp = [[10**18] * (h + 1) for _ in range(n)]
    dp[0] = [((i + a - 1) // a) * b for i in range(h + 1)]
    for i in range(1, n):
        a, b = m[i]
        for j in range(h + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= a:
                dp[i][j] = min(dp[i][j], b + dp[i][j - a])

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


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

arr = [0] * (h+1)
# arr[k] := hpがkの敵を倒すのに必要な最小魔力

arr[1] = min([ele[1] for ele in hp_and_magic])
for i in range(2, h+1):
    arr[i] = 10 ** 9
    for ele in hp_and_magic:
        if i-ele[0] >= 0:
            arr[i] = min(arr[i], arr[i-ele[0]] + ele[1])
            # print(arr[i-ele[0]], ele[1])

print(arr[h])

Submission status: Wrong Answer

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

    dp = [float("inf")]*(H + 10010)
    mx = 10**8
    for a,b in AB:
        dp[a] = min(dp[a],b)
    for i in range(1,H + 1):
        if dp[i] > mx:
            continue
        for a,b in AB:
            dp[i + a] = min(dp[i + a],dp[i] + b)
    for j in range(H,10000):
        if dp[j] < mx:
            print(dp[j])
            return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


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


H, N = inpl()
AB = [inpl() for i in range(N)]
AB.sort()

ans = [0] + [AB[0][1]] * AB[0][0] + [sys.maxsize for i in range(H - AB[0][0])]

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

print(ans[H])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, n = map(int, input().split())
    m = [tuple(map(int, input().split())) for _ in range(n)]

    a, b = m[0]
    dp = [[10**9] * (h + 1) for _ in range(n)]
    dp[0] = [((i + a - 1) // a) * b for i in range(h + 1)]
    for i in range(1, n):
        a, b = m[i]
        for j in range(h + 1):
            dp[i][j] = dp[i - 1][j]
            if j >= a:
                dp[i][j] = min(dp[i][j], b + dp[i][j - a])

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


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(N)]
h = max(ab[:][0])
dp = [[10**9]*(H+1+h) for _ in range(N+1)]
dp[0][0]=0
for i in range(N):
    for j in range(H+1+h):
        bb = ab[i][0]
        if j < bb:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-bb] + ab[i][1])
#print(dp)
print(min(dp[N][H:]))

Submission status: Wrong Answer

Solution code:
from math import floor
h,n = map(int,input().split())

magic = []
inf = float('INF')
dp = [inf for i in range(h+1)]
dp[0] = 0
for _ in range(n):
    a,b = map(int,input().split())
    for i in range(h+1):
        if i + a < h+1 and dp[i] + b < dp[i+a]:
            dp[i+a] = dp[i] + b
        elif i <= a and b < dp[i]:
            dp[i] = b
print(dp[h])
# print(dp)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
T = [(a, b, a / b) for a, b in AB]
T.sort(key=lambda t: t[2], reverse=True)

mp = T[0][1] * (H // T[0][0])
rem = H % T[0][0]
last = min(t[1] for t in T if t[0] >= rem) if rem >= 1 else 0
print(mp + last)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,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 LI_(): return [int(x)-1 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()
  v=[]
  w=[]

  for _ in range(n):
    a,b=LI()
    v.append(a)
    w.append(b)

  dp=[[0 for _ in range(h+10**6+100)] for __ in range(n+1)]

  for i in range(n):
    for j in range(h+10**6+100):
      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])

  # mx=0
  # for x in dp:
  #   # print(x[:h+1])
  #   mx=max(mx,max(x))
  # print(mx)


  ans=inf
  for x in dp:
    for i,y in enumerate(x):
      if h<=y:
        ans=min(ans,i)

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h+1 + 10**4)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h+1+10**4):
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = b
print(dp[-1][h-1])

Submission status: Wrong Answer

Solution code:
H,N=[int(i) for i in input().split(" ")]


A=[]
B=[]
magics=[]
for i in range(N):
    a,b=[int(j) for j in input().split(" ")]
    magics.append((a,b))


magics=sorted(magics,key=lambda w:w[0]/w[1], reverse=True)
bMin=10**10
for m in magics:
    if m[1]<=bMin:
        A.append(m[0])
        B.append(m[1])
        bMin=m[1]

N=len(A)



tables=[[0 for i in range(H+1)] for j in range(N+1)]
for i in range(1,H+1):
    tables[0][i]=10**10

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

print(tables[-1][-1])

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
H,N = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(key=itemgetter(1))

dp = [10**9]*(H+1)
dp[0] = 0
for i in range(1, H+1):
    for j in range(N):
        if i < L[j][0]:
            continue
        dp[i] = min(dp[i], L[j][1]+dp[i-L[j][0]])

print(dp[H])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
m=[]
for i in range(n):
  m.append(l[i][1])
x=min(m)
dp=[999999999999 for i in range(h+1)]
dp[0]=0
for i in range(h+1):
  for j in range(n):
    if i>=l[j][0]:
      dp[i]=min(dp[i-l[j][0]]+l[j][1],dp[i])
  dp[i]=min(dp[i-1]+x,dp[i])
print(dp[h])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
inf = 10**12
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
dp = [[inf for i in range(h+1 + 10**4)] for j in range(n+1)]
dp[0][0] = 0
for i in range(n):
    a, b = data[i]
    for j in range(h):
        if j - a >= 0:
            dp[i+1][j] = min(dp[i+1][j-a] + b, dp[i][j])
        else:
            dp[i+1][j] = b
print(dp[-1][h-1])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
m=[]
for i in range(n):
  m.append(l[i][1])
x=min(m)
dp=[999999999999 for i in range(h+1)]
dp[0]=0
for i in range(h+1):
  for j in range(n):
    if i>=l[j][0]:
      dp[i]=min(dp[i-l[j][0]]+l[j][1],dp[i])
  if dp[i]==999999999999:
    dp[i]=dp[i-1]+x
print(dp[h])

Submission status: Wrong Answer

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

C = [a/b for a,b in zip(A, B)]

X = [[a, b, c] for a, b, c in zip(A, B, C)]
X.sort(key=lambda x: x[2])

n = H / X[-1][2]
print(int(n) if int(n)==n else int(n+1))