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:
# coding: utf-8

import numpy as np

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

    abc.sort(key=lambda x: x[1])
    abc.sort(key=lambda x: x[0], reverse=True)
    ri = set()
    for i in range(1, N):
        if abc[i][1] > abc[i-1][1]:
            ri.add(i)
    ri = set(ri)
    abc_ = []
    for i in range(N):
        if i not in ri:
            abc_.append(abc[i])

    abc = abc_

    HD = defaultdict(lambda : INF)
    _, b, a = abc[0]
    for i in range(1, dc(H, a)+1):
        HD[H - i*a] = i*b
    for _, b, a in abc[1:]:
        tmp = {}
        for k, v in list(HD.items()):
            for i in range(1, dc(k, a)+1):
                if HD[k - i*a] > v+i*b:
                    HD[k- i*a] = v+i*b
        # HD.update(tmp)
    ans = INF
    for k, v in HD.items():
        if k <= 0:
            ans = min(ans, v)


    return ans


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500000)

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = 2 * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

h, n = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
dp = dict()
print(f(n - 1, h))

Submission status: Wrong Answer

Solution code:
import unittest


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(9, [[8, 3], [4, 2], [2, 1]]), 4)

    def test_2(self):
        self.assertEqual(think(100, [[1, 1], [2, 3], [3, 9], [4, 27], [5, 81], [6, 243]]), 100)

    def test_3(self):
        self.assertEqual(think(
            9999,
            [
              [540, 7550], [691, 9680], [700, 9790],
              [510, 7150], [415, 5818], [551, 7712],
              [587, 8227], [619, 8671], [588, 8228],
              [176, 2461]
            ]
        ), 139815)


def solve():
    h, list_of_a_and_b = read()
    result = think(h, list_of_a_and_b)
    write(result)


def read():
    h, n = read_int(2)
    list_of_a_and_b = []
    for _ in range(n):
        list_of_a_and_b.append(read_int(2))
    return h, list_of_a_and_b


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(h, list_of_a_and_b):
    list_of_ratio_and_a_and_b = []
    for a, b in list_of_a_and_b:
        list_of_ratio_and_a_and_b.append((a / b, a, b))

    list_of_ratio_and_a_and_b.sort(key=lambda x: -x[0])
    return recursive_solve(list_of_ratio_and_a_and_b, 0, h)


def write(result):
    print(result)


def recursive_solve(list_of_ratio_and_a_and_b, index, remain):
    min_of_a = 1
    max_of_b = 10 ** 4
    max_of_h = 10 ** 4
    inf = (max_of_h // min_of_a) * max_of_b + 1

    if index >= len(list_of_ratio_and_a_and_b):
        return inf
    ratio_and_a_and_b = list_of_ratio_and_a_and_b[index]  # (a / b, a, b)
    a, b = ratio_and_a_and_b[1], ratio_and_a_and_b[2]
    if remain % a == 0:
        return b * (remain // a)
    else:
        ret = inf
        if remain <= a:
            ret = b
        next_remain = remain - a * (remain // a)
        ret = min(
                ret,
                b * (remain // a + 1),
                b * (remain // a) + recursive_solve(list_of_ratio_and_a_and_b, index + 1, next_remain)
        )
        return ret


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Wrong Answer

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

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

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

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

print(dp[n][h])

Submission status: Wrong Answer

Solution code:
import math
line = input().split(' ')
H = int(line[0])
N = int(line[1])
min_m = 100000
t = 0
As = []
Ms = []
mins = 100000
for i in range(N):
  line = input().split(' ')
  As.append(int(line[0]))
  Ms.append(int(line[1]))
  if min_m > Ms[i]/As[i]:
    min_m = Ms[i]/As[i]
    t = i
for i in range(t,N):
  if min_m == Ms[i]/As[i] and Ms[i] < Ms[t]:
      t = i
ans = math.floor(H/As[t])*Ms[t]
k = H%As[t]
if k == 0:
  print(ans)
else:
  for i in range(N):
    if Ms[i] >= Ms[t]:
      continue
    elif As[i] < k:
      continue
    else:
      t = i
  print(ans+Ms[t])

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)

max_A = max(A)
dp = [[float('inf') for _ in range(H + max_A + 1)] for _ in range(N + 2)]
for i in range(N+2):
    dp[i][0] = 0

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

# print(dp)
for h in range(H, H + max_A + 1):
    if not (dp[N][h] == float('inf')):
        print(dp[N][h])
        exit()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(1000000000)

def dfs(i, hit):
    if i == N - 1:
        return MAGICS[i][1]
    if hit <= 0:
        return 0
    if (hit - MAGICS[i][0]) >= 0:
        return  MAGICS[i][1] + dfs(i, hit - MAGICS[i][0])
    else:
        return dfs(i + 1, hit)


H, N = map(int, input().split())
MAGICS = [list(map(int, input().split())) for _ in range(N)]
MAGICS = list(reversed(sorted(MAGICS, key=lambda m: m[0] / m[1])))
print(dfs(0, H))

Submission status: Wrong Answer

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

dp = [-1] * (h+1)
dp[0] = 0

init_min_cost = 0
for a, b in ab_list:
    if init_min_cost == 0:
        init_min_cost = b
    else:
        init_min_cost = min(init_min_cost, b)

for i, cost in enumerate(dp):
    if i == 0:
        continue

    min_cost = 0

    for a, b in ab_list:
        if i - a >= 0:
            if min_cost == 0:
                min_cost = dp[i-a] + b
            else:
                min_cost = min(min_cost, dp[i-a] + b)

    if min_cost == 0:
        min_cost = init_min_cost

    # dp[i] = min(min_cost, dp[i-1] + init_min_cost)
    dp[i] = min_cost
    # print(dp)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
m=[[0,0,0] for _ in range(n)]
L=100000000000
mina=1000000
minb=1000000
for i in range(n):
  a,b=map(int,input().split())
  m[i]=[a,b]
  if b<minb:
    minb=b
    mina=a
dp=[L for _ in range(h+1)]
dp[0]=0
for i in range(1,h+1):
  for j in range(n):
    [a,b]=m[j]
    if i>=a:
      dp[i]=min(dp[i-a]+b,dp[i])





print(dp[-1])

Submission status: Wrong Answer

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

ans = float("inf")

for i in range(n):
    h0 = h
    count_b = 0
    while h0 > 0:
        h0 -= l[i][0]
        count_b += l[i][1]
        if h0 <= l[i][1]:
            break
    
    
    remainder = 0
    if count_b < ans:
        ans = count_b
        remainder = h0

last_b = float("inf")

for i in range(n):
    if remainder <= l[i][0] and last_b > l[i][1]:
        last_b = l[i][1]

ans += last_b
    
print(ans)

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
B = {i:A[i][0]/A[i][1] for i in range(N)}
C = sorted(list(B.items()),key=lambda x:x[1],reverse=True)
cmin = 10**8
cnt = 0
cur = 0
while cur<N:
    if H>=A[cur][0]:
        cnt += (H//A[cur][0])*A[cur][1]
        H = H%A[cur][0]
    cmin = min(cmin,cnt+A[cur][1])
    cur += 1
print(cmin)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
CAB = []
for i in range(N):
    A_, B_ = input().split()
    CAB.append([int(A_)/int(B_), int(A_), int(B_)])

B_cons = 0


def masort(CAB):
    CAB = sorted(CAB, reverse=True)

    return CAB


def change_C(CAB, H):  # A>Hの箇所は全てA=H
    for cab in CAB:
        if cab[1]>H:
            cab[1] = H
            cab[0] = cab[1] / cab[2]

    return CAB


CAB = change_C(CAB, H)
CAB = masort(CAB)

while(H>0):
    if CAB[0][1]<=H:
        H -=CAB[0][1]
        B_cons+=CAB[0][2]
    else:  # 効率的な技が変わっている可能性を考慮する必要がある
        CAB = change_C(CAB, H)
        CAB = masort(CAB)

        H -= CAB[0][1]
        B_cons += CAB[0][2]

print(B_cons)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H,N=map(int, input().split())
arts=[]
point=[]
DPS=[]
for i in range(N):
    x,y=map(int, input().split())
    z=x/y
    arts.append(x)
    point.append(y)
    DPS.append(z)
num=DPS.index(max(DPS))
c=arts[num]
if H%c==0:
    print(point[num]*(H//c))
else:
    print(point[num]*(H//c)+min(point))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]
#i-1番目までの魔法で、j以上のだめを得与えるのに最低限必要な魔力
infi=10**12
dp=[[infi]*(h+10**4+1) for i in range(n+1)]
#shoki化
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(h+10**4+1):
        if j-AB[i][0]>=0:
            dp[i+1][j]=min(dp[i][j], dp[i+1][j-AB[i][0]]+AB[i][1])
        else:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j])
flag=0
for i in range(h, h+10**4+1):
    if dp[n][i]!=infi and flag==0:
        print(dp[n][i])
        flag=1

Submission status: Wrong Answer

Solution code:
import bisect

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

dp = [0] * (10 ** 6)

for i in range(n):
    for j in range(lst[i][1], len(dp)):
        dp[j] = max(dp[j - lst[i][1]] + lst[i][0], dp[j - 1], dp[j])


print(bisect.bisect_left(dp, h))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
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)  # コスパ順


def attack(h, magics):
    cost = magics[0][1] * (h // magics[0][0])
    return h % magics[0][0], cost


_, c = attack(H, T)
mp = 0
cands = [c + T[0][1]]
while H >= 1:
    magic_cand = [t for t in T if t[0] <= H]
    if len(magic_cand) >= 1:
        H, c = attack(H, magic_cand)
        mp += c
    else:
        break

    if H == 0:
        cands.append(mp)
        break
    else:
        cands.append(mp + c)  # もう一撃で削り切る
print(min(cands))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import pprint
import math
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 = [[float('inf') for _ in range(10**4+1)] for _ in range(N + 5)]
for i in range(N+5):
    dp[i][0] = 0

for i in range(N):
    for h in range(10**4+1):
        dp[i + 1][h] = min(dp[i + 1][h], dp[i][h])
        if h >= A[i]:
            dp[i + 1][h] = min(dp[i + 1][h], dp[i + 1][h - A[i]] + B[i])

# print(dp)
for h in range(H, 10**4+1):
    if not (dp[N][h] == float('inf')):
        print(dp[N][h])
        exit()

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[]
ans=1000000000000007
for i in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
d=[0]*20005
for i in range(10002):
    for j in l:
        a,b=j[0],j[1]
        x=d[i]+b
        if d[i]!=0 and d[i+a]!=0:
            d[i+a]=min(d[i+a],x)
        elif i==0 or (d[i]!=0 and d[i+a]==0):
            d[i+a]=x
for i in range(h,20005):
    if d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

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

Submission status: Wrong Answer

Solution code:
import math
line = input().split(' ')
H = int(line[0])
N = int(line[1])
min_m = 100000
t = 0
As = []
Ms = []
mins = 100000
for i in range(N):
  line = input().split(' ')
  As.append(int(line[0]))
  Ms.append(int(line[1]))
  if min_m > As[i]/Ms[i]:
    min_m = As[i]/Ms[i]
    t = i
for i in range(t,N):
  if min_m == As[i]/Ms[i] and Ms[i] < Ms[t]:
      t = i
ans = math.floor(H/As[t])*Ms[t]
k = H%As[t]
if k == 0:
  print(ans)
else:
  for i in range(N):
    if Ms[i] >= Ms[t]:
      continue
    elif As[i] < k:
      continue
    else:
      t = i
  print(ans+Ms[t])

Submission status: Wrong Answer

Solution code:
#E - Crested Ibis vs Monster
H,N = map(int,input().split())
A =[list(map(int, input().split())) for i in range(N)]
tmp = 0
ans = 0
for i in range(N):
    A[i].append(A[i][0]-A[i][1])

A.sort(key=lambda x: x[2],reverse = True)
min_A = min(A, key = lambda x:x[1])

while tmp < H - A[0][0]:
    tmp += A[0][0]
    ans += A[0][1]

if tmp < H:
    while tmp < H:
        tmp += int(min_A[0])
        ans += int(min_A[1])
else:
    pass

print(ans)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
a = {}
for i in range(n):
    v, k = map(int,input().split())
    a[v] = [k, v/k]
b = sorted(a.items(), key=lambda x:x[1][1], reverse=True)
c = sorted(a.items(), key=lambda x:x[1][0], reverse=False)
MP = 0
while h > 0:
    for i in range(n):
        if b[i][0] < h:
            h -= b[i][0]
            MP += b[i][1][0]
            break
        else:
            if h <= c[i][0]:
                h -= c[i][0]
                MP += c[i][1][0]
                break

print(MP)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]
#i-1番目までの魔法で、j以上のだめを得与えるのに最低限必要な魔力
infi=10**12
dp=[[infi]*(2*h+1) for i in range(n+1)]
#shoki化
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(2*h+1):
        if j-AB[i][0]>=0:
            dp[i+1][j]=min(dp[i][j], dp[i+1][j-AB[i][0]]+AB[i][1])
        else:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j])
flag=0
for i in range(h, 2*h):
    if dp[n][i]!=infi and flag==0:
        print(dp[n][i])
        flag=1

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,a,b])
ab.sort(reverse=True)
ans = (h//ab[0][1])*ab[0][2]
o = h-(h//ab[0][1])*ab[0][1]
f = [i[2] for i in ab if i[1] >= o]
add = 0
if o > 0 and f != []:
  add = min(f)
print(ans+add)

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

count = int(H/lst[0][0])
rest = H - count*lst[0][0]
magic = count*lst[0][1]

if rest == 0:
  a = magic
else:
  for i in range(N):
    if rest > lst[i][0]:
      a = magic + lst[i-1][1]
      print(i)
      break
    if i == N-1:
      a = magic + lst[N-1][1]

print(a)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():

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

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

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


main()

Submission status: Wrong Answer

Solution code:
h,n = map(int, input().split())
ab,e = [],[]
for i in range(n):
  a,b = map(int, input().split())
  ab.append([a/b,a,b])
ab.sort(reverse=True)
ans = (h//ab[0][1])*ab[0][2]
o = h-(h//ab[0][1])*ab[0][1]
f = [i[2] for i in ab if i[1] >= o]
add = 0
if f != []:
  add = min(f)
print(ans+add)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,N=map(int,input().split())
    A,B=[0]*N,[0]*N
    for i in range(N):
        A[i],B[i]=map(int,input().split())
    dp=[[INF]*(10**4*3) for _ in range(N+1)]
    dp[0][0]=0
    ans=INF
    for i in range(N):
        for hp in range(H+2):
            if hp>=A[i]:
                dp[i+1][hp]=min(dp[i][hp],dp[i+1][hp])
                dp[i+1][hp]=min(dp[i+1][hp],dp[i][hp-A[i]]+B[i])
                dp[i+1][hp]=min(dp[i+1][hp],dp[i+1][hp-A[i]]+B[i])
            else:
                dp[i+1][hp]=min(dp[i][hp],dp[i+1][hp])
            if hp>=H:
                ans=min(ans,dp[i+1][hp])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
inputs = input().split(" ")
h = int(inputs[0])
n = int(inputs[1])

class Magic:
    def __init__(self, damage, mp):
        self.damage = damage
        self.mp = mp
        self.rate = damage / mp
    def __lt__(self, other):
        if self.rate < other.rate:
            return True
        elif other.rate < self.rate:
            return False
        return self.damage < other.damage

magics = []
for i in range(n):
    inputs = input().split(" ")
    magics.append(Magic(int(inputs[0]), int(inputs[1])))

magics = sorted(magics, reverse=True)

count = 0
for m in magics:
    num = h // m.damage
    if 1 <= num:
        h -= m.damage * num
        count += m.mp * num

if 0 < h:
    last = magics[0]
    for m in magics:
        if h <= m.damage and m.mp < last.mp:
            last = m
    count += last.mp

print(count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
H, N=map(int, input().split())
AB=[list(map(int, input().split())) for _ in range(N)]
AB=sorted(AB, key=itemgetter(0))

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

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[]
ans=1000000000000007
chk=0
for i in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
d=[0]*20005
for i in range(10002):
    for j in l:
        a,b=j[0],j[1]
        x=d[i]+b
        if d[i]!=0 and d[i+a]!=0:
            d[i+a]=min(d[i+a],x)
        elif i==0 or d[i]!=0:
            d[i+a]=x
for i in range(h,20005):
    if d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Submission status: Wrong Answer

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

dp = [-1] * h
dp[0] = 0

init_min_cost = 0
for a, b in ab_list:
    if init_min_cost == 0:
        init_min_cost = b
    else:
        init_min_cost = min(init_min_cost, b)

for i, cost in enumerate(dp):
    min_cost = 0

    for a, b in ab_list:
        if i - a >= 0:
            if min_cost == 0:
                min_cost = dp[i-a] + b
            else:
                min_cost = min(min_cost, dp[i-a] + b)

    if min_cost == 0:
        min_cost = init_min_cost

    # print(dp)
    dp[i] = min_cost

print(dp[-1])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
l=[]
ans=1000000007
chk=0
for i in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
d=[0]*20005
for i in range(10002):
    for j in l:
        a,b=j[0],j[1]
        x=d[i]+b
        if d[i]!=0 and d[i+a]!=0:
            d[i+a]=min(d[i+a],x)
        elif i==0 or d[i]!=0:
            d[i+a]=x
for i in range(h,20005):
    if d[i]!=0:
        ans=min(ans,d[i])
print(ans)

Submission status: Wrong Answer

Solution code:
INFTY = 10**8
H,N = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
dp = [[INFTY for _ in range(H+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0
for i in range(1,N+1):
    for h in range(1,H+1):
        dp[i][h] = dp[i-1][h]
        if h>=A[i-1][0]:
            dp[i][h] = min(dp[i][h],dp[i][h-A[i-1][0]]+A[i-1][1])
    for h in range(H-1,0,-1):
        if dp[i][h]>dp[i][h+1]:
            dp[i][h] = dp[i][h+1]
print(dp[N][H])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
d=sorted([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,s):
        if p[j]>p[j-a]+b:
            p[j]=p[j-a]+b
print(min(p[h:]))