Emergency Rations

Time limit1sMemory limit128 MB

Summary

Choose boxes with a capacity and an expiry day to eat one unit daily starting day 1; report the last reachable day and the fewest boxes needed.

Level: Medium7 of 10
Topics: Greedy, Sorting, Intervals, Binary search
Solved: No attempts yet

Problem

You have prepared for the coming apocalypse by building an underground bunker. Now you need to fill that bunker with food and other rations so you can last as long as possible.

Emergency rations come in boxes, and every box is the same size. Each box has two properties: (1) how many units of consumption it holds ( $D_i$ ), and (2) how many days after the apocalyptic event it expires, after which it can no longer be consumed (its expiration date $E_i$ ).

You must consume your first unit of rations on day $1$ and then exactly one unit every day after that, without a break. A box with expiration date $X$ that holds $Y$ units can be consumed on up to $Y$ different days, and only on days less than or equal to $X$ . For example, a box with expiration date $3$ worth $2$ units can be consumed on days $1$ and $2$ , or days $2$ and $3$ , or days $1$ and $3$ , or even on day $3$ alone (leaving the box only partially consumed).

You want to know the last day $D$ on which you can still eat without ever breaking your daily streak. Because every box is the same size and you do not want to waste bunker space, you also want the minimum number of boxes $B$ needed to last through day $D$ .

Input

The first line contains the number of data sets $K$ . Then $K$ data sets follow, each in the form below.

The first line of each data set contains the integer $N$ ( $1 \le N \le 1000$ ), the number of emergency ration boxes you may choose from to store in your bunker. Two lines of $N$ integers each follow. The $i$ -th integer on the first line is the number of days $D_i$ that box $i$ will last you (that is, how many units it can be consumed for), and the $i$ -th integer on the second line is the expiration date $E_i$ of box $i$ . Every $D_i$ and $E_i$ is between $1$ and $1{,}000{,}000{,}000$ inclusive.

Output

For each data set, first output Data Set x: on a line by itself, where $x$ is its number. On the next line, output two integers $D$ and $B$ separated by a single space, where $D$ is the last day you can consume rations and $B$ is the minimum number of boxes needed to reach day $D$ . Output a blank line after each data set.

Examples3

Example 1

Input

Expected output

Data Set 1:
7 1

Data Set 2:
11 2

Data Set 3:
3 3

Example 2
Input
```
1
1
3
10
```
Expected output
```
Data Set 1:
3 1
```
Example 3
Input
```
1
1
100
5
```
Expected output
```
Data Set 1:
5 1
```