CEO 검색

Code Jam의 CEO가 컴퓨터 프로그래밍의 예술과 더 많은 시간을 보내기 위해 막 은퇴했으므로, 새로운 사람을 찾는 데 여러분의 도움이 필요하다!

모든 Code Jam 직원은 음이 아닌 정수인 경력 수준을 가진다. 새로운 CEO를 고용할 때 Code Jam 팀을 다음과 같이 구성해야 한다.

• CEO를 제외한 모든 직원은 자신의 경력 수준보다 높은 경력 수준을 가진 다른 직원 한 명을 직속 관리자로 두어야 한다. (CEO는 직속 관리자를 둘 수 없다.)

• 경력 수준이 E인 직원(CEO 포함)은 0명 이상 E명 이하의 다른 직원에 대한 직속 관리자가 될 수 있다. 직원 A가 직원 B의 직속 관리자이고 B가 C의 직속 관리자라면, A가 C의 직속 관리자이기도 한 것은 아니라는 점에 유의하라.

• 사내 정치 때문에 새로운 CEO는 기존 직원 중 한 명일 수 없고, 그 밖의 새 직원을 추가할 수 없으며, 기존 직원을 제거할 수도 없다.

물론 경력이 더 많은 CEO를 고용할수록 비용이 더 많이 든다! 위 규칙에 따라 Code Jam 팀을 구성할 수 있게 하는 새로운 CEO의 가능한 최소 경력 수준은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 모든 i < j에 대해, $E_{i}$ < $E_{j}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ L ≤ 10. 1 ≤ $N_{i}$ ≤ 10. 모든 $N_{i}$의 합은 ≤ 10. 0 ≤ $E_{i}$ ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ L ≤ 1000. 1 ≤ $N_{i}$ ≤ $10^{12}$. 0 ≤ $E_{i}$ ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 기존 직원들에게 존재하는 서로 다른 경력 수준의 수를 나타내는 정수 L이 적힌 한 줄로 시작한다. 그다음 L개의 줄이 주어진다. 이 중 i번째 줄에는 두 정수 $N_{i}$와 $E_{i}$가 주어지며, 경력 수준이 $E_{i}$인 기존 직원이 $N_{i}$명 있음을 나타낸다.

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

예제 케이스 #1에는 기존 직원이 다섯 명 있다. 경력 수준이 3인 직원이 한 명, 경력 수준이 2인 직원이 두 명, 경력 수준이 0인 직원이 두 명이다. 경력 수준이 4인 새로운 CEO를 고용할 수 있다. 그러면 예를 들어, 새로운 CEO가 수준 3인 직원과 수준 0인 직원 한 명을 직접 관리하게 하고, 수준 3인 직원이 수준 2인 직원 두 명과 수준 0인 나머지 직원을 직접 관리하게 할 수 있다. (다른 유효한 구성도 가능하다.) 더욱이 새로운 CEO는 적어도 수준 4이어야 한다. 그렇지 않으면 기존의 수준 3인 직원을 직접 관리할 수 있는 사람이 아무도 없기 때문이다. 따라서 4은 상한이면서 하한이므로 반드시 정답이다.

예제 케이스 #2에서는 기존 직원 다섯 명 모두의 경력 수준이 0이며 다른 직원을 직접 관리할 수 없다. 새로운 CEO가 이들 모두를 직접 관리해야 하며, 그러려면 경력 수준이 적어도 5이어야 한다.