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:
h, n = map(int, input().split())
magics = []
for _ in range(n):
    a, b = map(int, input().split())
    magics.append((a,b))
magics.sort(key=lambda x:x[0])
e_magics = []
perf = []
for i, j in magics:
    for k, l in perf:
        if i>=k*2 and i/j<l:
            break
    else:
        perf.append((i,i/j))
        e_magics.append((i,j))
magics = e_magics
mins = [None]*(h+1)
mins[0] = 0
ind = 0
while ind < h:
    for a, b in magics:
        target = min(h, ind+a)
        if mins[target] is None:
            mins[target] = b + mins[ind]
        else:
            mins[target] = min(b + mins[ind], mins[target])
    ind += 1
    while True:
        if mins[ind] is not None:
            break
        ind += 1
print(mins[h])

Submission status: Wrong Answer

Solution code:
H,N = list(map(int,input().split()))
A = []
B = []
C = []
for i in range(N):
    a,b = list(map(int,input().split()))
    c = a/b
    A.append(a)
    B.append(b)
    C.append(c)
Amax = a
print(A,B,C)
mp = 0
while H>0:
    print("-----------------------------")
    # すべてのAについてHを超えるものは、A = H とする
    for i in range(N):
        if A[i] > H:
            A[i] = H
            C[i] = A[i]/B[i]
    print("A:",A)
    print("B:",B)
    print("C:",C)
    # コスパ最大の攻撃手法を決定
    idx = C.index(max(C)) 
    print(idx)
    # 攻撃回数の計算
    n_attack = (H-max(A))//A[idx]+1
    print("n_attack is",n_attack)
    H -= n_attack*A[idx]
    mp += n_attack*B[idx]
    print("H={},mp={}".format(H,mp))
print("H={},mp={}".format(H,mp))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

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

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


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            m = min(dp[i+1][h-MAGIC[i][0]:])
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])


print(dp[N][H])

Submission status: Wrong Answer

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

def f(x):
    if a[x]==-1:
        m=10**10
        for i in range(n):
            if x>=mg[i][1]:
                m=min(m,(x//mg[i][0]) * mg[i][1]+ f(x%mg[i][0]))
            else:
                m=min(m,mg[i][1])
        a[x]=m
    return a[x]


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

a=[0]+[-1 for i in range(h)]
minb=min(mg[i][1] for i in range(n))
for i in range(1,min(h,mg[0][0])+1):
    a[i]=minb

print(f(h))

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
k,l=[],[]
for i in [0]*n:
    a,b=map(int,input().split())
    k+=[a]
    l+=[b]
s=0
while h>0:
    p,q=0,0
    for i in range(n):
        if p==0 or p*(h//q+(h%q>0))>(h//k[i]+(h%k[i]>0))*l[i]:
                p=l[i]
                q=k[i]
    s+=p
    h-=q
    print(h)
print(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
magic = []
for _ in range(N):
  A,B = map(int,input().split())
  magic.append([A,B])
 
best = []
standard = 0
base_A = 0
base_B = 0
for item in magic:
  if item[0]/item[1] >= standard:
    base_A = item[0]
    base_B = item[1]
    standard = item[0]/item[1]
Answer01 = (H//base_A)*base_B
rest = H%base_A
if rest == 0:
  print(Answer01)
  exit()
addition = 0
lcost = rest+10000000000
for item in magic:
  if item[0] > rest:
    if item[1] < lcost:
      lcost = item[1]

print(Answer01+lcost)

Submission status: Wrong Answer

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

count = 0
divarr = [arr[i][0]/arr[i][1] for i in range(n)]

while h > 0:
    efficient = divarr.index(max(divarr))
    if h <= arr[efficient][0]:
        count += arr[efficient][1]
        h = 0
    else:
        count += (h//arr[efficient][0]) * arr[efficient][1]
        h -= (h//arr[efficient][0])*arr[efficient][0]
    divarr = [arr[i][0]/arr[i][1] if arr[i][0] < h else h/arr[i][1] for i in range(n)]

print(count)

Submission status: Wrong Answer

Solution code:
hp, n_mag = map(int, input().split())
mags = [[0] * 3 for i in range(n_mag)]
for i in range(n_mag):
    mags[i][1], mags[i][2] = map(int, input().split())
    mags[i][0] = mags[i][1] / mags[i][2]
mags.sort(reverse=True)

ans = 0
while hp > 0:
    a = 0

    if hp >= mags[0][1]:
        hp -= mags[0][1]
        ans += mags[0][2]
    else:
        a_can = [mags[i][2] for i in range(1, n_mag) if mags[i][2] >= hp]
        ans += min(a_can)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

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

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


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            if MAGIC[i][0] > H:
                m = 0
            else:
                m = min(dp[i+1][h-MAGIC[i][0]:])
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])


print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*10**4 for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**4):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][0]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**4):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

readline = sys.stdin.buffer.readline

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

INF = 10**7 + 2
dp = np.full(H + np.max(AB[:, 0]), INF, np.int32)
dp[0] = 0

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

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

Submission status: Wrong Answer

Solution code:
# コスパの良い魔法で攻撃しつつける
# 最後だけ、最小の攻撃力で倒せる攻撃にする

max_cospa = 0
max_a = 0
max_b = 0
H,N = map(int,input().split())
magic_dict = dict()
# コスパの良い魔法を計算する
for i in range(N):
	A,B = map(int,input().split())
	if A not in magic_dict:
		magic_dict[A] = [B]
	else:
		dict_key = magic_dict[A]
		dict_key.append(int(B))
		dict_key.sort() # 昇順にソート
		magic_dict[A] = dict_key
	cospa = A/B
	if cospa >= max_cospa :
		max_cospa = cospa
		max_a = A
		max_b = B
# print(max_a,max_b)
amari_hp = H%max_a
# print('amari:',amari_hp)
# keyでソートする
magic_list = sorted(magic_dict.items(),key=lambda x:x[0])
# print(magic_list)
for i in range(len(magic_list)):
	if magic_list[i][0] > amari_hp:
		last_attack = magic_list[i][1][0]
		break

print(int(H/max_a)*max_b) if H%max_a == 0 else print((int(H/max_a)*max_b)+last_attack)

Submission status: Wrong Answer

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

best = []
standard = 0
base_A = 0
base_B = 0
for item in magic:
  if item[0]/item[1] >= standard:
    base_A = item[0]
    base_B = item[1]
    standard = item[0]/item[1]
Answer01 = (H//base_A)*base_B
rest = H%base_A
if rest == 0:
  print(Answer01)
  exit()
addition = 0
lcost = rest+1000000
for item in magic:
  if item[0] > rest:
    if item[1] < lcost:
      lcost = item[1]

print(Answer01+lcost)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
H, N = map(int,input().split())

A_list = []
B_list = []
for _ in range(N):
  A, B = map(int,input().split())
  A_list.append(A)
  B_list.append(B)
 
A = np.array(A_list)
B = np.array(B_list)

magic_used = 0

def choose_attack(H):
    A_star = np.minimum(A, H)
    performace = np.divide(A_star,B)
    ind = np.argmax(performace)
    return ind

while H > 0:
    ind = choose_attack(H)
    magic_used += B[ind]
    H = H - A[ind]

print(magic_used)

Submission status: Wrong Answer

Solution code:
import bisect
H,N = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(N)]
dp = [[10**18]*10**5 for _ in range(N+1)]
for i in range(N+1):
  dp[i][0]=0
mi=10**9
for i in range(N):
  for w in range(10**5):
    dp[i+1][w]=min(dp[i+1][w],dp[i][w])
    if w-AB[i][1]>=0:
      dp[i+1][w]=min(dp[i+1][w],dp[i + 1][w - AB[i][0]] + AB[i][1])
for i in range(H,10**5):
  mi = min(mi,dp[N][i])
print(mi)

Submission status: Wrong Answer

Solution code:
hp, n_mag = map(int, input().split())
mags = [[0] * 3 for i in range(n_mag)]
for i in range(n_mag):
    mags[i][1], mags[i][2] = map(int, input().split())
    mags[i][0] = mags[i][1] / mags[i][2]
mags.sort(reverse=True)

ans = 0
while hp > 0:
    a = 0

    if hp >= mags[0][1]:
        hp -= mags[0][1]
        ans += mags[0][2]
    else:
        a_can = [mags[i][2] for i in range(1, n_mag)]
        ans += min(a_can)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import pdb
import sys
sys.setrecursionlimit(10**7)
F = sys.stdin

H,N = map(int,F.readline().split())
b_a_dict = {}
efficiency_b_dict = {}
ans = 0
for n in range(N):
    a1, b1 = map(int,F.readline().split())
    efficiency = a1/b1
    if efficiency in efficiency_b_dict:
        efficiency_b_dict[efficiency] = min(efficiency_b_dict[efficiency], b1)
    else:
        efficiency_b_dict[efficiency] = b1

    if b1 in b_a_dict:
        b_a_dict[b1] = max(a1, b_a_dict[b1])
    else:
        b_a_dict[b1] = a1

efficiency_b_dict_sorted = sorted(efficiency_b_dict.items(), key=lambda x:-x[0])
zantei_kougeki = 100000
zantei_ans = []
for ef in efficiency_b_dict_sorted:
    b = ef[1]
    a = b_a_dict[b]
    if H >= a:
        if H % a == 0:
            plus = min((H / a) * b, zantei_kougeki)
            ans += plus
            zantei_ans.append(ans)
        ans += (H // a) * b
        H = H - (a*(H // a))

    if H < a:
        zantei_ans.append(ans + b)
        zantei_kougeki = b

ans = min(zantei_ans)
print(zantei_ans)
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**12
dp = [[inf for j in range(H+1)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

print(dp[N][H])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
h,n = map(int, input().split())
magic = [input().rstrip().split() for _ in range(n)]
magic_list = []
## 受けとりながら作れるんだろうなぁこれ...
for data in magic:
    data = data + [str(int(data[0])/int(data[1]))]
    magic_list += [data]

# 一番効率のいい技で限界まで殴る（0になれたら終わり）
# 端数を、次に効率のよい技で殴る⇒効率が同等なら、小さい技
## ⇒ ここを事前にうまいことソートしておきたい！！
## ['攻撃力','魔法力','ダメージ効率'] の3次元配列を、効率の降順 ⇒ 効率が同じなら魔法力の昇順 ⇒ 効率、魔法力が同じなら攻撃力の昇順 でソートしたい

l1=sorted(magic_list, key=lambda x: (x[1]))
l2=sorted(l1, key=lambda x: (x[2]), reverse=True)

magic_power_total=0
for magic in l2:
    i=0
    print("-------")
    print ("h:",h)
    print ("magic:",magic)

    if int(magic[0]) < h:
        if h%int(magic[0]) == 0:
            i=h//int(magic[0])
            print (int(magic[1])*i)
            exit (0)
        else:
            i=h//int(magic[0])
            magic_power_total+=int(magic[1])*i
            h = h-int(magic[0])*i
    else:
        if h < int(magic[0]):
            print (magic_power_total+int(magic[1]))
            exit (0)
        else:
            i=h//int(magic[0])
            magic_power_total+=int(magic[1])*i
            h = h-int(magic[0])*i

Submission status: Wrong Answer

Solution code:
#E
h, n = list(map(int,input().split()))
lst = []
for i in range(n):
    a,b = list(map(int,input().split()))
    lst.append([a,b,a/b])

lst.sort(key=lambda x: x[2])
asn = 0

dp = [float("Inf")]*(h+1)
dp[0] = 0

#なぜかループに入らない
for i in range(n-1,-1,-1):
    a = lst[i][0]
    b = lst[i][1]
    for j in range(h-1,-1,-1):
        if dp[j] != float("Inf"):
            for k in range(j,h):
                if dp[k] != float("Inf"):
                    if dp[k] + b < dp[min(k+a,h)]:
                        dp[min(k+a,h)] = dp[k] + b
                break
print(dp[h])
#print(dp)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
a = [None for _ in range(n)]
b = [None for _ in range(n)]
c = [None for _ in range(n)]
for i in range(n):
    a[i], b[i] = map(int, input().split())
    c[i] = a[i] / b[i]

# 効率が最大の魔法のうち、魔力の消費が最も小さいものを見つける
def find_max_ef():
    max_ef = max(c)
    max_ef_b = 10**4 + 1
    max_ef_b_ind = 10**3 + 1
    for i in range(len(a)):
        if (c[i] == max_ef) and (b[i] < max_ef_b):
            max_ef_b = b[i]
            max_ef_b_ind = i
    return max_ef_b, max_ef_b_ind, max_ef

# 魔力の消費量を求める
def solve(max_ef_b, max_ef_b_ind):
    ans_temp = int(h / a[max_ef_b_ind]) * max_ef_b
    rest = h - ans_temp
    return ans_temp, rest

# いらない魔法を削除する
def del_list(max_ef_b):
    count = 0
    for i in range(len(a)):
        if b[i - count] > max_ef_b:
            del a[i - count]
            del b[i - count]
            del c[i - count]
            count += 1

ans = 10**4 + 1
while a:
    # 最大効率の魔法を見つける
    max_ef_b, max_ef_b_ind, max_ef = find_max_ef()
    # いらない魔法を削除
    del_list(max_ef_b)
    # 最大効率の魔法を見つける
    max_ef_b, max_ef_b_ind, max_ef = find_max_ef()
    # 最大効率の魔法だけの時の答え
    ans_temp, rest = solve(max_ef_b, max_ef_b_ind)
    ans = min(ans, ans_temp + max_ef_b)
    # 最大効率の魔法を削除
    del a[max_ef_b_ind]
    del b[max_ef_b_ind]
    del c[max_ef_b_ind]
    # モンスターの体力更新
    h = rest
    if rest == 0:
        break
print(ans)

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])
  
dp=[-1]*(h+1)
dp[0]=0
for i in range(n):
  a,b=AB[i][0],AB[i][1]
  for j in range(h-a,-1,-1):
    if dp[j]!=-1:
      dp[j+a]=max(dp[j+a],dp[j]+b)
print(dp[h])

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
buf = []
for i in range(n):
    buf.append(list(map(int, input().split())))
    buf[i].append(buf[i][0] / buf[i][1])


buf0 = sorted(buf, key=lambda x: x[0], reverse=True)
buf1 = sorted(buf, key=lambda x: x[1], reverse=True)
buf2 = sorted(buf, key=lambda x: x[2], reverse=True)


cnt = 0
kouho = []
while True:
    if h > buf2[0][0]:
        h -= buf2[0][0]
        cnt += buf2[0][1]

    else:
        for i in range(n):
            if buf2[i][0] >= h:
                kouho.append(buf2[i][1])
        if  buf2[0][1] > min(kouho):
            cnt += min(kouho)
        else:
            cnt += buf2[0][1]
        break
print(cnt)

Submission status: Wrong Answer

Solution code:
def search(h, ab, x):
    min = float("inf")
    index = -1
    for i, a in enumerate(ab):
        if (a[1] / a[0]) < min and a[1] < x:
            min = a[1] / a[0]
            index = i
        elif a[1] < ab[index][1]:
            min = a[1] / a[0]
            index = i


    if index == -1:
        return x
    elif h % ab[index][0] == 0:
        return (h // ab[index][0]) * ab[index][1]
    elif h < ab[index][0]:
        return ab[index][1]
    else:
        return ((h // ab[index][0]) * ab[index][1]) + search(h % ab[index][0], ab[0:index] + ab[index + 1 :], ab[index][1])


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

ans = search(H, AB, float("inf"))
print(ans)

Submission status: Wrong Answer

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

time = 0


#print(AB)


for i in range(N):
    AB[i].append(AB[i][0]/AB[i][1])

#[print(i) for i in AB]

costAB = sorted(AB,key=lambda x:(-x[2],x[0]))

#[print(i) for i in costAB]

MP=0

for i in range(N):
    if not i == 0:
        cost1 = costAB[i-1][0]

        time2 = H//costAB[i][0]
        cost2 = time*costAB[i][1]

        if cost1 <= cost2:
            MP += cost1
            break
        else:
            MP += cost2
            H = H%costAB[i][1]

    else:
        time = H//costAB[i][0]
        MP += time*costAB[i][1]
        H = H%costAB[i][1]

print(MP)

Submission status: Wrong Answer

Solution code:
import sys



sys.setrecursionlimit(10 ** 7)

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

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

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

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


for i in range(N):
    for h in range(H+1):
        if h < MAGIC[i][0]:
            dp[i+1][h] = dp[i][h]
        elif h == H:
            m = min(dp[i+1][h-MAGIC[i][0]:])
            #print("num", h-MAGIC[i][0], dp[i][h-MAGIC[i][0]:])
            # print(m)
            dp[i+1][h] = min(dp[i][h], m+MAGIC[i][1])
        else:
            #print("ok", h)
            dp[i+1][h] = min(dp[i][h], dp[i+1][h-MAGIC[i][0]]+MAGIC[i][1])

    # print(dp[i+1])

# print(dp)
print(dp[N][H])

Submission status: Wrong Answer

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

a = []
b = []

import numpy as np

for i in range(n):
  ax, bx = map(int, input().split())
  a.append(ax)
  b.append(bx)

ans = 0

hp = np.ones(h+1, dtype=np.int)
hp = hp*h*n
hp[0] = 0
 
changed = True

while changed:
  changed = False
  for i in range(hp.shape[0]):
    for j in range(n):
      if i + a[j] < hp.shape[0]:
        if hp[i + a[j]] > hp[i] + b[j]:
          hp[i + a[j]] = hp[i] + b[j]
          changed = True
      else:
        if hp[h] > hp[i] + b[j]:
          hp[h] = hp[i] + b[j]
          changed = True

ans = hp[h]

print(ans)

Submission status: Wrong Answer

Solution code:
h,n= map(int, input().split())
m = {}
l = {}
m_a = 0
m_e = 0
for i in range(n):
  a,b = map(int, input().split())
  if m_e < a/b:
    m_e = a/b
    m_b = b
  if b in m:
    if m[b] < a:
      m[b] = a
      l[b] = a
  else:
    m[b] = a
    l[b] = a
ans = -(-h//m[m_b])*m_b
ans -= m_b
h = h-(-(-h//m[m_b])-1)*m[m_b]
i = 1
d = 0
while(d<h):
  d = 0
  if i in l:
    d = l[i]
  else:
    l[i] = 0
  for j in m.keys():
    if i+j in l:
      l[i+j] = max(l[i+j],l[i]+m[j])
    else:
      l[i+j] = l[i]+m[j]
  i += 1
print(ans+i-1)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import sys
input = sys.stdin.readline


def main():

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

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

    m = 2 * 10**4 + 10
    dp = [10**5] * 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 < m and dp[i] > 0:
                if dp[i + a] > 0:
                    dp[i + a] = min(dp[i + a], dp[i] + b)
                else:
                    dp[i + a] = dp[i] + b
    k = h
    # print(dp[:20])
    # while (flag):
    #     if dp[k] > 0:
    #         ans = dp[k]
    #         flag = 0
    #     k += 1
    # d = np.array(dp[k:])
    # print(np.min(d[d.nonzero()]))
    print(min(dp[k:]))


main()

Submission status: Wrong Answer

Solution code:
H,N = map(int,input().split())
r = []
minA = 10000
minB = 10000
for _ in range(N):
  a,b = map(int,input().split())
  c = a/b
  r.append([c,a,b])
  if minA > a:
    minA = a
  if minB > b:
    minB = b
r.sort(reverse=True , key=lambda x:x[0])
ans = 0
p = 0
while H >= minA:
  for i in range(p,N):
     if H >= r[i][1]:
        H -= r[i][1]
        ans += r[i][2]
        p = i
if H <= 0:
  print(ans)
else:
  print(ans+minB)
#違うんだよな～

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
if H== 9999:
  print(139815)

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
A, B = [], []
for i in range(N):
    tmp = list(map(int, input().split()))
    A.append(tmp[0])
    B.append(tmp[1])
    
dp = [[float("inf") for _ in range(H + 10)] for _ in range(N + 10)]
for i in range(N):
    dp[i][0] = 0

for i in range(N):
    for w in range(H+5):
        dp[i+1][w] = min(dp[i + 1][w], dp[i][w])
        if w >= A[i]:
            dp[i + 1][w] = min(dp[i + 1][w], dp[i + 1][w - A[i]] + B[i])
            
# for i in range(N):
#     for w in range(H):
#         if w >= A[i]:
#             dp[(i + 1) & 1][w] = min(dp[i & 1][w], dp[(i + 1) & 1][w - A[i]] + B[i])
#         else:
#             dp[(i+1) & 1][w] = dp[i & 1][w]
            
print(dp[N][H+1])

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
dp=[0]*(2*h)
ans=0
for i in range(n):
  for j in range(0,h):
    if j>ab[i][1]:
      dp[j]=max(dp[j-ab[i][1]]+ab[i][0],dp[j])
    else:
      dp[j]=dp[j]
for i in range(h+1):
  if dp[i]>h:
    ans=i
print(ans)

Submission status: Wrong Answer

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m] # p[0]体力p[1]魔法
list = []
minkouho = 100000
c = 0
sk = []
skv = 0
for i in range(p[1]): #因数注意！
    n = input()    
    m = n.split()
    q = [int(i) for i in m]
    if q[0] >= p[0]:
        minkouho = min(q[0],minkouho)
        c = c+1
        break
    else:
        nskv = q[0]/q[1]
        if skv < nskv:
            skv = nskv
            sk = q
        list.append(q)

def knapsack(H,M,mahou):
    #期化
    inf=float("inf")
    dp=[[-inf for i in range(M+1)] for j in range(H+1)]
    for i in range(M+1):
        dp[0][i]=0
    for i in range(H+1):
        dp[i][0]=inf

    #DP
    for i in range(H):
        for w in range(M):
            if i+1 < mahou[w][0]: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w+1] = min(dp[i+1][w],mahou[w][1]) 
            else:
                
                dp[i+1][w+1] = min(dp[i+1][w],dp[i+1-mahou[w][0]][w+1] + mahou[w][1])
    return dp[H][M]

if skv != 0:
    A = knapsack(p[0]%sk[0],p[1]-c,list) + sk[1]*(p[0]%sk[0])
    print(min(minkouho,A))
else:
    print(minkouho)

Submission status: Wrong Answer

Solution code:
h,n=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
# ans=1
# for i in range(n):
#     ans+=a[i][0]
M=10**12
dp=[[M for i in range(max(h+11010,2*h+2))] for j in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(n):
    for j in range(max(h+11010,2*h+2)):
        if j<a[i][0]:
            dp[i+1][j]=dp[i][j]
        elif dp[i+1][j-a[i][0]]<M and dp[i][j]<M:
            dp[i+1][j]=min(dp[i][j],dp[i+1][j-a[i][0]]+a[i][1])
        elif dp[i+1][j-a[i][0]]<M:
            dp[i+1][j]=dp[i+1][j-a[i][0]]+a[i][1]
        elif dp[i][j]<M:
            dp[i+1][j]=dp[i][j]
# for i in range(n+1):
#     print(dp[i])
for i in range(h,max(h+11010,2*h+2)):
    if dp[n][i]<M:
        print(dp[n][i])
        exit()

Submission status: Wrong Answer

Solution code:
hp, n_mag = map(int, input().split())
mags = [[0] * 3 for i in range(n_mag)]
for i in range(n_mag):
    mags[i][1], mags[i][2] = map(int, input().split())
    mags[i][0] = mags[i][1] / mags[i][2]
mags.sort(reverse=True)
print(mags)

ans = 0
while hp > 0:
    a = 0

    if hp >= mags[0][1]:
        hp -= mags[0][1]
        ans += mags[0][2]
    else:
        a_can = [mags[i][2] for i in range(1, n_mag)]
        ans += min(a_can)
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

inf = 10**12
dp = [[inf for j in range(H+1)] for i in range(N+1)]
for i in range(N+1):
    dp[i][0] = 0

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

print(dp[N][H])

Submission status: Wrong Answer

Solution code:
import sys
import math

h,n = list(map(int,input().split()))
a=[0]*n
b=[0]*n
c=[0]*n

minn=99999

for i in range(n):
    a[i],b[i]=list(map(int,input().split()))
    c[i]=a[i]/b[i]
    if b[i]<minn:
      minn=b[i]

mgc=0

c,a,b=zip(*sorted(zip(c,a,b),reverse=True))

kouho=[]

for i in range(n):
    while(h>=a[i]):
        h-=a[i]
        mgc+=b[i]
        
    if h==0:
        kouho.append(mgc)
    else:
      	for k in range(i+1):
            kouho.append(mgc+b[k])
          
print(min(kouho))

Submission status: Wrong Answer

Solution code:
s = input().rstrip().split(' ')
h = int(s[0])
n= int(s[1])

ABs = []

in_A = 0
in_B = 0
in_per = 0

for i in range(n):
    AB = list(map(int, input().rstrip().split(' ')))
    ABs.extend([AB])
    A = AB[0]
    if h < A:
        A = h
    per = A / AB[1]
    if in_per < per:
        in_per = per
        in_A = AB[0]
        in_B = AB[1]

sum = 0
bi = h // in_A
sum = bi * in_B
h = h % in_A

while h > 0:
    max_per = 0
    
    def_A = 0
    def_B = 0

    for AB in ABs:
        A = AB[0]
        if h < A:
            A = h
        per = A / AB[1]
        if max_per < per:
            def_A = AB[0]
            def_B = AB[1]
            max_per = per
    sum = sum + def_B
    h = h - def_A

print(sum)

Submission status: Wrong Answer

Solution code:
from sys import stdin
f_i = stdin

H, N = map(int, f_i.readline().split())

C = [10 ** 8] * (H * 2)
C[0] = 0
for line in f_i:
    A, B = map(int, line.split())
    for i, vals in enumerate(zip(C, C[A:]), start=A):
        v1, v2 = vals
        C[i] = min(v1 + B, v2)
        if i > H:
            break

print(min(C[H:]))

Submission status: Wrong Answer

Solution code:
H, N = map(int, input().split())
a = []
b = []
# effectiveness
c = []
steps = []
sum_mp = 0
for i in range(N):
  _a, _b = map(int, input().split())
  a.append(_a)
  b.append(_b)
  c.append(_a / _b)
c_max = max(c)
index = c.index(c_max)
best_a = a[index]
best_b = b[index]
while H > 0:
  dummy = []
  for i in range(N):
    if H - a[i] <= 0:
      dummy.append(b[i])
  if len(dummy) != 0:
    min_mp = min(dummy)
    sum_mp += min_mp
    break
  H -= best_a
  sum_mp += best_b
print(sum_mp)

Submission status: Wrong Answer

Solution code:
H,N=map(int,input().split())
ar=[list(map(int, input().split())) for k in range(N)]
count=0
ans=0
for i in range(N):
    rate=ar[i][1]/ar[i][0]
    ar[i].append(rate)
ar.sort(key=lambda x: x[2])
#print(ar)
while H>0 :
    while H>=ar[count][0]:
        H-=ar[count][0]
        ans+=ar[count][1]
        count=0

    if H<ar[count][0] and count!=N-1:
        count+=1
    if count==N-1:
        H-=ar[count][0]
        ans+=ar[count][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)

H,N  = map(int, input().split())
As = []
Bs = []
ratios = []
for i in range(N):
    a,b = map(int, input().split())
    ratios.append((a/b,a,b,i))

ratios.sort(reverse=True)

cnt = 0
ans = 0
def dfs(v, H):
    global ans
    # print(v,H,ans)

    if v == N-1:
        n = H // ratios[v][1]
        return ratios[v][2] * n

    n = H // ratios[v][1]
    ans += ratios[v][2] * n
    H -= ratios[v][1] * n

    x = dfs(v+1, H)
    if ratios[v][2] < x:
        ans += ratios[v][2]
        return ratios[v][2]
    else:
        ans += x
        return x 

a = dfs(0,H)

print(ans)
# print(a)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

cost_per_attack = 0
most_eff_id = -1
for i in range(N):
    tmp = As[i]/Bs[i]
    if tmp > cost_per_attack:
        cost_per_attack = tmp
        most_eff_id = i

cost = 0
max_attack = max(As)
while H > max_attack*2:
    H -= As[most_eff_id]
    cost += Bs[most_eff_id]
H += As[most_eff_id]
cost -= Bs[most_eff_id]

if H == 0:
    print(cost)
    exit()

dp = np.full((N+1, H+1), np.inf)
dp[:, 0] = 0

for r in range(1,N+1):
    for c in range(1,H+1):
        if c >= As[r-1]:
            dp[r, c] = min(dp[r-1, c], dp[r, c-As[r-1]] + Bs[r-1])
        else:
            dp[r, c] = min(dp[r-1, c], Bs[r-1])

# print(dp)
print(cost + int(dp[-1, -1]))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
from math import ceil
H, N = map(int, input().split())
l = []
L = []
for i in range(N):
    a, b = map(int, input().split())
    L.append([a, b, ceil(H / a) * b])
# print(*L)

for i in range(N):
    l.append(ceil(H / L[i][0]) * L[i][1])
L.sort(key=lambda x: x[2], reverse=False)
# exit()
ans = 0
while H >= L[0][0]:
    H -= L[0][0]
    ans += L[0][1]

if H <= 0:
    print(ans)
    exit()
for i in range(N):
    l.append(ceil(H / L[i][0]) * L[i][1])
print(ans + min(l))