CEO 찾기

Code Jam의 CEO가 The Art of Computer Programming을 읽으며 지내려고 은퇴했다. 그래서 우리는 새 CEO를 찾는 데 당신의 도움이 필요하다!

Code Jam의 모든 직원은 음이 아닌 정수인 경력 수준을 가진다. 새 CEO를 뽑으면 Code Jam 팀을 다음과 같이 구성해야 한다.

• CEO를 제외한 모든 직원은 자신보다 경력 수준이 높은 다른 직원 한 명을 직속 상사로 두어야 한다. CEO는 직속 상사를 둘 수 없다.
• 경력 수준 E인 직원(CEO 포함)은 0명 이상 E명 이하의 직원을 직속 부하로 둘 수 있다. 직원 A가 직원 B의 직속 상사이고 B가 C의 직속 상사이더라도, A는 C의 직속 상사가 아니다.
• 사내 정치 때문에 새 CEO는 기존 직원이 될 수 없고, 다른 신입 직원을 추가할 수도 없으며, 기존 직원을 해고할 수도 없다.

경력이 높은 CEO를 뽑을수록 비용이 더 든다! 위 규칙에 따라 Code Jam 팀을 구성할 수 있게 하는 새 CEO의 경력 수준으로 가능한 최솟값은 얼마인가?

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 기존 직원들이 가진 서로 다른 경력 수준의 수 L이 주어진다. 그다음 L개의 줄이 주어지며, i번째 줄에는 두 정수 Ni와 Ei가 주어지고, 이는 경력 수준 Ei인 기존 직원이 Ni명 있음을 나타낸다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 새 CEO의 경력 수준으로 가능한 최솟값이다.

• 1 ≤ T ≤ 100.
• 모든 i < j에 대해 Ei < Ej.

예제 1에는 기존 직원이 다섯 명 있다. 경력 수준 3인 직원 한 명, 경력 수준 2인 직원 두 명, 경력 수준 0인 직원 두 명이다. 경력 수준 4인 새 CEO를 뽑으면, 예를 들어 새 CEO가 경력 수준 3인 직원과 경력 수준 0인 직원 한 명을 직속 부하로 두고, 경력 수준 3인 직원이 경력 수준 2인 직원 두 명과 나머지 경력 수준 0인 직원을 직속 부하로 둘 수 있다. 다른 구성도 가능하다. 또한 새 CEO가 경력 수준 4 미만이면 기존의 경력 수준 3인 직원을 직속 부하로 둘 사람이 없으므로, 새 CEO는 적어도 경력 수준 4여야 한다. 따라서 4는 상한이면서 하한이고, 정답이 된다.

예제 2에서는 기존 직원 다섯 명이 모두 경력 수준 0이라 다른 직원을 직속 부하로 둘 수 없다. 새 CEO가 이들 모두를 직접 직속 부하로 두어야 하므로 경력 수준이 적어도 5여야 한다.