비상 식량

시간 제한1초메모리 제한128 MB

요약

용량과 유통기한이 있는 상자를 골라 1일차부터 하루 한 단위씩 먹을 때, 도달할 수 있는 마지막 날과 필요한 최소 상자 수를 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 구간, 이분 탐색
정답자: 아직 제출이 없습니다

문제

다가올 종말에 대비하여 지하 벙커를 지었습니다. 이제 이 벙커를 식량과 각종 비상 식량으로 채워, 최대한 오래 버틸 수 있도록 해야 합니다.

비상 식량은 상자 단위로 들어오며, 모든 상자의 크기는 동일합니다. 각 상자는 두 가지 속성을 가집니다. (1) 며칠분( $D_i$ 일분)의 식량으로 소비할 수 있는지, (2) 종말 이후 며칠이 지나면 상해서 더 이상 먹을 수 없는지(유통기한 $E_i$ ).

첫째 날( $1$ 일)에 첫 번째 분량을 반드시 먹어야 하며, 그 뒤로는 매일 정확히 한 분량씩 거르지 않고 먹어야 합니다. 유통기한이 $X$ 이고 $Y$ 일분을 담은 상자는 서로 다른 최대 $Y$ 개의 날에 소비할 수 있으며, 그 날들은 모두 $X$ 일 이하여야 합니다. 예를 들어 유통기한이 $3$ 이고 $2$ 일분인 상자는 $1, 2$ 일에, 또는 $2, 3$ 일에, 또는 $1, 3$ 일에, 심지어 $3$ 일 하루에만(상자를 일부만 소비한 채) 먹을 수 있습니다.

하루도 거르지 않고 식량을 계속 먹을 수 있는 마지막 날 $D$ 를 알고 싶습니다. 또한 모든 상자의 크기가 같아 벙커 공간을 낭비하고 싶지 않으므로, $D$ 일까지 버티는 데 필요한 상자의 최소 개수 $B$ 도 알고 싶습니다.

입력

첫 줄에는 데이터 집합의 개수 $K$ 가 주어집니다. 이어서 $K$ 개의 데이터 집합이 각각 다음 형식으로 주어집니다.

각 데이터 집합의 첫 줄에는 벙커에 넣을 후보 비상 식량 상자의 개수 $N$ ( $1 \le N \le 1000$ )이 주어집니다. 그다음 각각 $N$ 개의 정수가 담긴 두 줄이 이어집니다. 첫째 줄의 $i$ 번째 정수는 상자 $i$ 가 버티게 해 주는 일수 $D_i$ (즉 소비할 수 있는 분량)이고, 둘째 줄의 $i$ 번째 정수는 상자 $i$ 의 유통기한 $E_i$ 입니다. 모든 $D_i$ 와 $E_i$ 는 $1$ 이상 $1{,}000{,}000{,}000$ 이하입니다.

출력

각 데이터 집합마다 먼저 그 번호 $x$ 를 사용하여 Data Set x:를 한 줄에 출력합니다. 다음 줄에는 두 정수 $D$ 와 $B$ 를 공백 하나로 구분하여 출력합니다. 여기서 $D$ 는 식량을 먹을 수 있는 마지막 날이고, $B$ 는 $D$ 일에 도달하는 데 필요한 상자의 최소 개수입니다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력합니다.

예제3

예제 1

입력

예상 출력

Data Set 1:
7 1

Data Set 2:
11 2

Data Set 3:
3 3

예제 2
입력
```
1
1
3
10
```
예상 출력
```
Data Set 1:
3 1
```
예제 3
입력
```
1
1
100
5
```
예상 출력
```
Data Set 1:
5 1
```