Bạn đang chơi một trò solitaire mới tên Prime Time. Bạn có một bộ bài, mỗi lá ghi một số nguyên tố; nhiều lá có thể ghi cùng số.

Mục tiêu là chia các lá thành hai nhóm sao cho tổng các số của nhóm thứ nhất bằng tích các số của nhóm thứ hai. Mỗi lá thuộc đúng một nhóm và mỗi nhóm phải có ít nhất một lá. Tổng hoặc tích của nhóm một lá chính là số trên lá đó.

Trong hình, nhóm trái có tổng \(25\), nhóm phải có tích \(25\), nên đây là cách chia hợp lệ. Điểm của bạn là tổng nhóm thứ nhất — cũng là tích nhóm thứ hai — hoặc bằng \(0\) nếu không thể chia. Hãy tìm điểm lớn nhất.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Dòng đầu mỗi bộ chứa \(M\), số lượng số nguyên tố phân biệt. Mỗi trong \(M\) dòng tiếp theo chứa \(P_i,N_i\), nghĩa là có đúng \(N_i\) lá ghi số nguyên tố \(P_i\). Tổng số lá là \(\sum_iN_i\).

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)), còn \(y\) là điểm lớn nhất.

Ràng buộc

• \(1\le T\le100\); \(1\le M\le95\) (có đúng \(95\) số nguyên tố từ \(2\) đến \(499\)).
• \(2\le P_i\le499\); mọi \(P_i\) nguyên tố; \(P_i<P_{i+1}\).
• \(N_i\ge1\) với mọi \(i\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le\sum N_i\le10\).
• Test Set 2 (Visible Verdict): \(2\le\sum N_i\le100\).
• Test Set 3 (Hidden Verdict): \(2\le\sum N_i\le10^{15}\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7

Case #1: 25
Case #2: 17
Case #3: 0
Case #4: 8

Nguồn

Google Code Jam 2021, Vòng 1A, bài Prime Time.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.