풀이 방법

힙을 이용해야 한다.
데이터 사이즈가 정렬을 하게 되면 시간초과가 난다.
그렇기 때문에 최대 heap으로 구현 후, 다시 루프를 돌면서 빼내가며 최대 금액을 출력해줘야 한다.

풀이 코드

import sys
import heapq

w, n = map(int, sys.stdin.readline().split())

ls = []
for i in range(n):
    total, kg = map(int, sys.stdin.readline().split())
    heapq.heappush(ls, (-kg, -total))

res = 0

for i in range(len(ls)):
    kg, tot = heapq.heappop(ls)
    kg = - kg
    tot = - tot
    if w >= tot:
        res += tot * kg
        w -= tot
    else:
        res += w * kg
        break

print(res)