시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB419927736.150%

문제

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

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

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

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

입력

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

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

출력

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

제한

  • $1 \le N \le 100\,000$
  • $1\,000N \le X \le 5\,000N$
  • $1 \le A \le 10,000$, $1 \le B \le 10,000$

예제 입력 1

3 9000
40 10
20 5
30 20

예제 출력 1

65

첫째 날에는 5,000원짜리 메뉴를, 둘째 날과 셋째 날에는 1,000원짜리 메뉴를 사 먹는 것이 가장 현명하다.

예제 입력 2

1 1000
30 10

예제 출력 2

10

준원이의 수중에 1,000원밖에 없어서 1,000원짜리 메뉴를 먹을 수밖에 없는 경우이다.

예제 입력 3

1 5000
10 30

예제 출력 3

30

1,000원짜리 메뉴가 더 맛있다면 돈이 남더라도 1,000원짜리 메뉴를 주문할 수도 있다.

출처

University > 제주대학교 > 2021 하반기 취업 알고리즘 집중특강 및 해커톤 대회 A번