| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 472 | 354 | 328 | 77.910% |
한양대학교는 2023년부터 Hanyang Popularity Exceeding Competition을 열게 되었다. 이 대회는 일정 기간 진행되며, 대회가 끝나는 시점에 인기도가 가장 높은 학생이 우승한다. 철민이는 Hanyang Popularity Exceeding Competition의 참가자이지만, 이제 막 학교에 다니기 시작한 철민이는 인기도가 0ドル$밖에 되지 않는다.
철민이는 한양대학교 내의 유명인 $N$명과 만난다는 우승 계획을 세웠다. 이를 위해 철민이는 1ドル$번 유명인부터 $N$번 유명인까지 차례대로 만날 계획을 세웠다.
하지만 현실은 생각보다 복잡해서, 유명인들과 만난다고 항상 인기도가 올라가지는 않는다. 한쪽의 유명도가 다른 한쪽에 비해 너무 높으면 한쪽의 인기에 다른 쪽이 묻혀버리기 때문이다. 엄밀히 말해서, 철민이의 현재 인기도를 $X$라고 하고, $i$번 유명인의 인기도를 $P_i,ドル 친화력을 $C_i$라고 하자. 이때, $|P_i-X|\le C_i$여야 철민이의 인기도가 1ドル$ 올라간다. $|P_i-X|>C_i$라면 철민이의 인기도는 변하지 않는다.
그래서 철민이는 모든 유명인을 다 만나는 대신, 일부 유명인만을 골라 만나서 인기도를 최대화하려고 한다. 이때, 철민이가 도달할 수 있는 최대 인기도는 얼마일까?
유명인들은 바쁜 삶을 보내기 때문에, 유명인과 만나는 시간을 변경할 수는 없다. 즉, 번호가 더 높은 유명인을 먼저 만나도록 계획을 변경할 수는 없다.
첫 번째 줄에 한양대학교의 유명인들의 수 $N$이 주어진다. $(1\le N\le 200,円 000)$
다음 $N$개의 줄의 $i$번째 줄에는 $i$번 유명인의 인기도와 친화력을 의미하는 두 정수 $P_i,C_i$가 공백으로 구분되어 주어진다. $(0\le P_i,C_i\le 500)$
첫 번째 줄에 철민이가 도달할 수 있는 최대 인기도를 출력한다.
3 1 1 0 0 2 1
2
아래 방식으로 만남을 계획하면 인기도를 최대화할 수 있다.
5 0 0 0 1 0 2 0 3 0 4
5
모든 유명인을 만나면 인기도를 최대로 올릴 수 있다.
3 4 3 3 2 2 1
0
어떤 방식으로 만남을 계획해도 철민이의 인기도가 오를 수 없다.