白俊解答1106ホテル

#낮은 가격순으로 순회하며 업데이트 시켜줄것이기 때문
advertise.sort(key=lambda x : x[0]) 
# C+100을 해준이유는 최소값이 C를 초과한 경우에 생기는 케이스가 있을 수 있음
dp = [INF]*(C+100) #100은 문제의 조건에 있음 홍보로 얻을수 있는 고객의 최대값
dp[0] = 0 #테이블 초기화

#테이블 업데이트
for cost, new_pep in advertise:
    for i in range(new_pep, C+100):
        dp[i] = min(dp[i-new_pep] + cost, dp[i])

import sys
input = sys.stdin.readline
INF = 1e9
C, N = map(int, input().split()) #c ->늘려야할 최소고객수, N - > 도시개수
advertise = []

for _ in range(N):
    temp = list(map(int, input().split())) #비용, 고객수
    advertise.append(temp)

advertise.sort(key=lambda x : x[0])

dp = [INF]*(C+100)
dp[0] = 0

for cost, new_pep in advertise:
    for i in range(new_pep, C+100):
        dp[i] = min(dp[i-new_pep] + cost, dp[i])

print(min(dp[C:]))