시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 20 9 8 72.727%

문제

승엽이는 전역을 일주일 앞둔 최고참 말년 병장이다. 부대 내에서 아무도 승엽이를 막을 수 없다.

승엽이의 취미는 후임들이 작업이나 근무 나갔을 때 후임들의 관물장을 열어 간식을 뺏어먹는 것이다.

승엽이가 배부름을 느낄 수 있는 포만감 정도인 ‘충분 포만감’ M 은 정해져 있고, 간식을 먹어 M 만큼 포만감을 느끼는 것이 목적이다. 승엽이는 M 이상 포만감을 채우지 못하면 화가 난다.

승엽이는 누구 간식을 뺏어 먹을지 고민하다가, 가장 만만한 후임인 현철이에게 자신이 배부를 만큼 간식을 가져오라고 시켰다.

현철이는 후임들을 괴롭히는 승엽이가 괘씸해서, 최대한 승엽이가 덜 좋아하는 간식들만 골라서 가져갈 생각이다.

평소 승엽이는 PX에 판매하는 모든 간식에 대해 얼마나 맛있는지 만족도를 평가해 두었다.

고생하는 현철이를 도와 승엽이가 배를 채우며 얻을 수 있는 최소의 만족도를 계산해 보자!

입력

첫 줄에 후임의 수 N (1 ≤ N ≤ 100), 승엽이의 충분 포만감 M (1 ≤ M ≤ 100,000) 이 공백을 두고 주어진다.

다음 개의 줄에 각각 해당 후임의 간식을 뺏어 먹고 얻을 수 있는 포만감 W (1 ≤ W ≤ 1,000)와 만족도 H (1 ≤ H ≤ 1,000)가 공백을 두고 주어진다.

출력

첫 줄에 승엽이가 충분 포만감 만큼 포만감을 채우며 얻을 수 있는 최소의 만족도를 한 줄로 출력한다.

승엽이가 간식으로 충분 포만감을 채울 수 없는 경우 “죄송합니다 한승엽 병장님” 을 한 줄로 출력한다.

서브태스크 1 (50점)

  • ≤ 25

서브태스크 2 (50점)

  • 추가 제한 조건은 없다.

예제 입력 1

4 6
5 10
2 6
3 5
4 4

예제 출력 1

9

승엽이의 충분 포만감은 6이고, 2번째와 4번째 간식을 먹어 충분 포만감 6에 도달하고 10의 만족도를 얻을 수 있다.

하지만 3번째와 4번째 간식을 먹으면 포만감 7로 충분 포만감을 넘으면서 더 낮은 만족도 9를 얻을 수 있다.

예제 입력 2

2 10
3 5
4 1

예제 출력 2

죄송합니다 한승엽 병장님

모든 간식을 먹어도 포만감이 7 밖에 되지 않아서 승엽이의 충분 포만감인 10에 도달하지 못한다.

채점

  • 예제는 채점하지 않는다.