문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제한 사항

• 1 ≤ N ≤ $10^6$인 정수
• 1 ≤ W ≤ $10^4$인 정수
• 1 ≤ Mi, Pi ≤ $10^4$인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

100 2
90 1
70 2

출력예제1

170

풀이

아이디어

이 문제는 배낭문제 중에 아이템들을 쪼갤 수 있는 분할 가능한 배낭 문제에 해당한다. 따라서, 가치(가격)이 가장 높은 순서대로 아이템들을 최대 힙에 넣어놓고 무게*가격을 계속 정답에 합산하다가 어느순간 가방 용량이 현재 아이템 무게보다 작아지는 순간이 오는데, 그 아이템은 현재 정답에 맞게 쪼개서 그만큼의 가치를 곱해준 값을 정답에 더한다.

코드

from heapq import heappush, heappop
import sys
capacity, N = map(int, sys.stdin.readline().split())
heap = []
answer = 0

for i in range(N):
  weight, value = map(int, sys.stdin.readline().split())
  heappush(heap, (-value, weight))

while heap and capacity:
  v, w = heappop(heap)
  if capacity >= w:
    answer -= v*w
    capacity -= w
  else:
    answer -= v*capacity
    capacity = 0

print(answer)