시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 20 | 9 | 8 | 66.667% |
승엽이는 전역을 일주일 앞둔 최고참 말년 병장이다. 부대 내에서 아무도 승엽이를 막을 수 없다.
승엽이의 취미는 후임들이 작업이나 근무 나갔을 때 후임들의 관물장을 열어 간식을 뺏어먹는 것이다.
승엽이가 배부름을 느낄 수 있는 포만감 정도인 ‘충분 포만감’ M 은 정해져 있고, 간식을 먹어 M 만큼 포만감을 느끼는 것이 목적이다. 승엽이는 M 이상 포만감을 채우지 못하면 화가 난다.
승엽이는 누구 간식을 뺏어 먹을지 고민하다가, 가장 만만한 후임인 현철이에게 자신이 배부를 만큼 간식을 가져오라고 시켰다.
현철이는 후임들을 괴롭히는 승엽이가 괘씸해서, 최대한 승엽이가 덜 좋아하는 간식들만 골라서 가져갈 생각이다.
평소 승엽이는 PX에 판매하는 모든 간식에 대해 얼마나 맛있는지 만족도를 평가해 두었다.
고생하는 현철이를 도와 승엽이가 배를 채우며 얻을 수 있는 최소의 만족도를 계산해 보자!
첫 줄에 후임의 수 N (1 ≤ N ≤ 100), 승엽이의 충분 포만감 M (1 ≤ M ≤ 100,000) 이 공백을 두고 주어진다.
다음 N 개의 줄에 각각 해당 후임의 간식을 뺏어 먹고 얻을 수 있는 포만감 W (1 ≤ W ≤ 1,000)와 만족도 H (1 ≤ H ≤ 1,000)가 공백을 두고 주어진다.
첫 줄에 승엽이가 충분 포만감 만큼 포만감을 채우며 얻을 수 있는 최소의 만족도를 한 줄로 출력한다.
승엽이가 간식으로 충분 포만감을 채울 수 없는 경우 “죄송합니다 한승엽 병장님
” 을 한 줄로 출력한다.
4 6 5 10 2 6 3 5 4 4
9
승엽이의 충분 포만감은 6이고, 2번째와 4번째 간식을 먹어 충분 포만감 6에 도달하고 10의 만족도를 얻을 수 있다.
하지만 3번째와 4번째 간식을 먹으면 포만감 7로 충분 포만감을 넘으면서 더 낮은 만족도 9를 얻을 수 있다.
2 10 3 5 4 1
죄송합니다 한승엽 병장님
모든 간식을 먹어도 포만감이 7 밖에 되지 않아서 승엽이의 충분 포만감인 10에 도달하지 못한다.
University > 건국대학교 > 2019 건국대학교 동아리 알프스 프로그래밍 경진대회 (KAPC) H번