문제

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

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

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

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

# 23559
import sys
input = lambda: sys.stdin.readline().strip()

# 메뉴 A와 B의 맛 차이로 힙에 추가
# 5000원이 가능한 날 만큼 A 메뉴 선택
# 단, A보다 B가 더 맛있을 경우 B메뉴 선택

import heapq

n, x = map(int, input().split())
day = []
for _ in range(n):
    menu = list(map(int, input().split()))
    heapq.heappush(day, (menu[1] - menu[0], menu[0], menu[1]))
    
flavor = 0
for i in range(n):
    dif, a, b = heapq.heappop(day)
    if x >= 5000 and (x - 5000) // 1000 >= (n - (i+1)) and a > b:
        flavor += a
        x -= 5000
    else:
        flavor += b
        x -= 1000
        
print(flavor)

백준 23559 밥