가장 순서에 맞는 방법

면접 대비

시간 제한0.3초메모리 제한1024 MB

요약

각 과제의 소요 시간 T와 마감 D가 주어질 때, 모든 과제를 마감 안에 끝내는 사전순 가장 앞선 순서를 구하고, 없으면 *을 출력합니다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

소피아는 학교에서 $N$ 개의 과제를 받았다. 과제는 1부터 $N$ 까지 번호가 매겨져 있다. 각 과제에는 두 값 $T$ 와 $D$ 가 있다. $T$ 는 과제를 끝내는 데 걸리는 시간(분)이고, $D$ 는 지금부터 $D$ 분 이내에 끝내야 하는 마감 시간이다.

소피아는 과제를 원하는 순서로, 한 번에 하나씩 할 수 있다. 일단 시작한 과제는 끝날 때까지 계속한다. 소피아는 시간을 과제를 하는 데만 쓴다. 바로 시작할 수 있고, 과제 하나를 끝내면 쉬지 않고 곧바로 다음 과제를 시작한다.

소피아는 완벽주의자라서 모든 과제를 끝내고 싶어 한다. 처음에는 주어진 순서대로 하려고 했지만, 그러면 일부 과제가 마감을 넘긴다는 것을 곧 깨달았다. 모든 과제를 제시간에 끝내는 순서가 여럿이라면, 가장 순서에 맞는 방법을 원한다. 소피아가 일을 어떻게 배치해야 하는지 알려 주는 프로그램을 작성하시오.

시간 제한: 300 ms. 메모리 제한: 1024 MB.

입력

첫 줄에 정수 $N$ ( $1 \le N \le 5000$ )이 주어진다. 다음 $N$ 개 줄에는 각각 정수 $T$ 와 $D$ ( $1 \le T \le D \le 10^9$ )가 주어진다.

출력

1부터 $N$ 까지 정수의 순열을 한 줄에 출력한다. 이 순서대로 과제를 하면 모든 과제가 마감 안에 끝난다. 그런 순서가 없으면 *(별표)를 출력한다. 가능한 순열이 여러 개면 사전순으로 가장 앞선 것을 출력한다.

예제4

예제 1
입력
```
2
5 9
5 9
```
예상 출력
```
*
```
예제 2
입력
```
3
6 6
2 9
2 1000
```
예상 출력
```
1 2 3
```
예제 3
입력
```
3
6 6
2 1000
2 9
```
예상 출력
```
1 3 2
```
예제 4
입력
```
3
30 100
20 100
10 100
```
예상 출력
```
1 2 3
```