생존자 (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$ 가 공백을 두고 주어진다.

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