밥

면접 대비

시간 제한1초메모리 제한256 MB

요약

N일 동안 두 메뉴 중 하나를 매일 골라 총예산 X 안에서 맛있기 점수의 합이 최대가 되도록 한다.

문제

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

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

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

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

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

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

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