문제
당신은 무인도에 조난당했다. 다행히 음식이 들어있는 상자를 하나 챙길 수 있었지만, 풀 한 포기 보이지 않는 돌섬인데다 낚시를 할 방법이 없어서 추가적인 음식 공급은 어려운 상황이다.
잠깐의 확인을 통해, 음식이 전체 N개이고, 각 음식 i에 대해 남아 있는 유통기한 Pi와 먹으면 얼마 동안 허기를 참을 수 있는지를 나타내는 Si에 대한 조사가 끝난 상황이다.
한편, 음식을 먹는 데는 다음과 같은 제약사항이 있다.
지금부터 음식을 먹기 시작한다.
남아있는 유통기한 Pi와 허기를 참을 수 있는 기간을 나타내는 Si의 단위는 '분'으로 같다.
유통기한이 지난 음식은 바로 폐기한다. 즉, 남아있는 유통기한이 0인 음식은 지금 바로 먹지 않으면 폐기해야 하는 음식이다.
허기를 참을 수 있는 기간에는 다른 아무것도 먹지 않는다.
허기가 오기 시작하자마자 무언가 먹지 않으면 바로 굶어 죽는다.
이런 조건이 있을 때, 무인도에서 얼마만큼 생존할 수 있는지 구해보자.
입력
입력의 첫 줄에는 음식의 개수 N이 주어지고, 다음 줄부터 N개의 줄에 음식의 유통기한 Pi와 허기를 참을 수 있는 기간 Si가 공백으로 구분하여 주어진다.
<제약조건>
모든 입력은 정수로 주어진다.
작은 데이터는 1 ≤ N ≤ 10. 0 ≤ Pi ≤ 100. 1 ≤ Si ≤ 100 를 만족한다.
큰 데이터는 1 ≤ N ≤ 1000. 0 ≤ Pi ≤ 100000. 1 ≤ Si ≤ 1000 를 만족한다.
출력
무인도에서 생존할 수 있는 최대 시간 y를 출력하시오.
예제 #1
3
3 4
0 4
4 4
8
예제 #2
3
3 9
0 4
4 4
9
출처
Code Jam Korea 2012 본선 라운드
로그인해야 코드를 작성할 수 있어요.