프라임 타임
시간 제한45초메모리 제한1024 MB
소수 카드 묶음을 두 개의 비어 있지 않은 그룹으로 나누어 한쪽 합과 다른 쪽 곱이 같아지도록 하고, 그 공통값의 최댓값을 구한다.
문제
새로운 카드 게임인 프라임 타임을 하고 있다. 카드 한 벌이 주어지고, 각 카드에는 소수가 적혀 있다. 같은 수가 적힌 카드가 여러 장 있을 수 있다.
카드를 두 그룹으로 나누어, 첫 번째 그룹에 있는 수의 합이 두 번째 그룹에 있는 수의 곱과 같도록 만들어야 한다. 각 카드는 정확히 두 그룹 중 하나에 속해야 하고, 각 그룹에는 카드가 최소 한 장 있어야 한다. 카드가 한 장뿐인 그룹의 합이나 곱은 그 카드에 적힌 수와 같다.
예를 들어 위 그림에서 왼쪽 그룹은 카드의 합이 25이고 오른쪽 그룹은 카드의 곱이 25이다. 따라서 이는 올바른 그룹 나누기이다.
점수는 첫 번째 그룹에 있는 수의 합(두 번째 그룹에 있는 수의 곱과 같다)이며, 이렇게 카드를 나눌 수 없으면 0이다. 얻을 수 있는 최대 점수는 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 카드에 있는 서로 다른 소수의 개수를 나타내는 정수 M이 주어진다. 다음 M개 줄에는 각각 두 값 Pi와 Ni가 주어지는데, 이는 소수 Pi가 적힌 카드가 정확히 Ni장 있음을 나타낸다.
카드 한 벌의 전체 카드 수는 모든 Ni의 합이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 얻을 수 있는 최대 점수이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ M ≤ 95. (2와 499 사이에는 정확히 95개의 서로 다른 소수가 있다)
- 2 ≤ Pi ≤ 499, 모든 i에 대해.
- 각 Pi는 소수이다.
- Pi < Pi+1, 모든 i에 대해. (소수는 엄격히 증가하는 순서로 주어진다)
- 1 ≤ Ni, 모든 i에 대해.
힌트
예제 1에서 최적의 분할은 11+2+7+3+2=5⋅5이다. 5+7+3+2+5=11⋅2로 나눌 수도 있지만 점수가 더 낮다.
예제 2에서는 같은 수가 적힌 카드를 서로 다른 그룹에 놓을 수 있다.