시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 381 | 76 | 66 | 22.837% |
피앳산은 세상에서 가장 깨끗한 청정수가 샘솟기로 유명한 산이다. 피앳산의 등산객들은 이 청정수를 마시기 위해 매일같이 산을 올랐다. 피앳산엔 아무리 사용해도 오염되지 않는 천 년 묵은 표주박이 있었기에 모든 등산객들이 청정수를 마실 수 있었다.
하지만 어느 날 천 년 묵은 표주박이 사라지고 말았다. 표주박이 사라졌기 때문에 더 이상 청정수를 마시는 것은 불가능하다. 청정수에 중독된 등산객들은 물을 마실 도구를 찾기 위해 온 산을 뒤졌고, 덜 자란 표주박 하나를 발견했다. 이를 발견한 이는 곧바로 두 쪽으로 나눈 뒤 물을 마시기 시작했지만, 어느 순간 표주박이 오염되고 있다는 사실을 깨달았다. 곧바로 다른 쪽 표주박으로 물을 마시려던 등산객은 다른 사람들에게 발각되어 저지당했다.
등산객들은 남은 반쪽으로 최대한 많은 사람이 청정수를 마시기 위한 방법을 생각하고 있다.
각 등산객이 물을 마시게 되면 표주박의 오염도가 일정량 증가하게 된다. 또한 현재 표주박의 오염도가 자신의 임계치 이상인 등산객은 물을 마시려 하지 않는다.
이 까다로운 등산객들을 위해 최적의 방법을 알려주자.
첫째 줄에 등산객의 수 $N(1 \le N \le 1\,000)$이 주어진다.
이후 $N$개의 줄에 두 개의 정수 $p_i(1 \le p_i \le 100)$와 $c_i(1 \le c_i \le 3\,000)$가 주어진다. $p_i$는 $i$번째 등산객이 표주박을 오염시키는 정도, $c_i$는 초기 오염도를 기준으로 $i$번째 등산객의 임계치를 의미한다.
첫째 줄에 청정수를 마실 수 있는 사람 수의 최댓값, 최대로 마신 후의 오염도를 출력한다.
그러한 경우가 여러가지라면, 오염도가 최소가 되도록 한다.
4 1 3 2 3 4 2 3 5
3 6
5 1 4 3 4 2 2 5 1 3 7
4 9