생존자 (Large)

당신은 무인도에 조난당했다. 음식이 든 상자 하나는 챙겼지만, 풀 한 포기 없는 돌섬이고 낚시할 방법도 없어서 음식을 더 구할 수는 없다.

상자를 확인해 보니 음식은 모두 $N$개다. 각 음식 $i$에는 남은 유통기한 $P_i$와 그 음식을 먹으면 허기를 참을 수 있는 시간 $S_i$가 적혀 있다. 두 값의 단위는 모두 분이다.

음식을 먹는 규칙은 다음과 같다.

• 지금, 즉 0분부터 음식을 먹기 시작한다.
• 유통기한이 지난 음식은 즉시 폐기한다. 현재 시각이 $t$분이면 $P_i \ge t$인 음식만 먹을 수 있다. 남은 유통기한이 0인 음식은 지금 당장 먹지 않으면 폐기해야 한다.
• 음식 $i$를 $t$분에 먹으면 $t + S_i$분이 될 때까지 다른 것은 아무것도 먹지 않는다.
• $t + S_i$분이 되는 순간 다른 음식을 먹지 못하면 곧바로 굶어 죽는다.

무인도에서 버틸 수 있는 최대 시간을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 다음 형식이다.

첫 줄에 음식의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 음식 하나의 남은 유통기한 $P_i$와 허기를 참을 수 있는 시간 $S_i$가 공백을 두고 주어진다.

제약조건

• 모든 입력은 정수다.
• $1 \le T \le 100$
• $1 \le N \le 1000$
• $0 \le P_i \le 100000$
• $1 \le S_i \le 1000$

각 테스트 케이스 $x$마다 무인도에서 버틸 수 있는 최대 시간 $y$를 Case #x: y 형식으로 한 줄에 출력한다.