비상 식량

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

비상 식량은 상자 단위로 들어오며, 모든 상자의 크기는 동일합니다. 각 상자는 두 가지 속성을 가집니다. (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$일에 도달하는 데 필요한 상자의 최소 개수입니다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력합니다.