백준-23559번(밥)-python

문제

제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다.

준원이는 대면 수업이 시작되는 바람에 이제 남은 학기의 �$N$일동안 매일 학식의 두 메뉴 중 정확히 하나를 골라서 먹어야 한다. N일간의 두 메뉴는 이미 공지되어 있고, 준원이는 이미 모든 날의 각 메뉴가 얼마나 맛있을지 수치를 매겨 두었다.

준원이는 N일간 학식에 총 X원 이하를 써야 한다.

여러분이 N일간 준원이의 메뉴를 잘 골라서, 고른 메뉴의 맛의 합을 최대화 해주자!

입력

첫째 줄에는 두 정수 N, X가 주어진다.

둘째 줄부터 N개의 줄에, 각 날에 먹을 수 있는 5,000원짜리 메뉴의 맛 A와 1,000원짜리 메뉴의 맛 B가 공백을 사이에 두고 주어진다.

출력

준원이가 고른 메뉴들의 맛의 합을 최대화했을 때의 값을 출력하라.

예제 입력 1

3 9000
40 10
20 5
30 20

예제 출력 1

65

예제 입력 2

1 1000
30 10

예제 출력 2

10

예제 입력 3

1 5000
10 30

예제 출력 3

30

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

Ah=[]	#맛의 차이 A-B를 저장할 힙

N,X=map(int,input().split())    #N일동안 X원 만큼 사용가능

sum=0   #맛의 최댓값을 넣는 변수

for i in range(N):
    A,B=map(int,input().split())
    heappush(Ah,(-(A-B),A-B)) #최대힙
    sum+=B	#맛의 최댓값에 1000원짜리 맛의 가치를 더해줌
    
X-=N*1000	#일단 1000원짜리를 다 담았으므로 일수*1000을 해서 X원에서 빼줌

while X>=4000 and Ah[0][1]>0:	#5000-1000이므로 남은돈이 4000원이상 이고, A-B가 양수일경우 반복문 수행
    sum+=heappop(Ah)[1]	#A-B가 최대인 양수값을 맛의 최댓값 변수에 더해줌
    X-=4000	#남은 돈에서 4000원을 빼줌
print(sum)