ABCDEFG 23

Tác giả:

quanghieu18112013

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(7\) số tự nhiên \(A, B, C, D, E, F, G\). Hãy tìm cách chia \(7\) số này thành hai tập hợp con rời nhau: tập \(S_1\) chứa đúng \(4\) phần tử và tập \(S_2\) chứa đúng \(3\) phần tử sao cho:

Tổng các phần tử trong tập \(S_1\) bằng tổng các phần tử trong tập \(S_2\).
Tích các phần tử trong tập \(S_1\) đạt giá trị lớn nhất có thể.

Yêu cầu: Hãy in ra tích lớn nhất của các phần tử trong tập \(S_1\) tìm được. Nếu không tồn tại bất kỳ cách chia nào thỏa mãn điều kiện tổng bằng nhau, hãy in ra \(-1\).

Input

Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) — số lượng bộ dữ liệu.
\(T\) dòng tiếp theo, mỗi dòng chứa \(7\) số tự nhiên \(A, B, C, D, E, F, G\) (\(0 \le A, B, C, D, E, F, G \le 2\times 10^4\)).

Output

In ra \(T\) dòng, mỗi dòng chứa một số nguyên duy nhất là tích lớn nhất thu được của tập \(S_1\), hoặc \(-1\) nếu không có phương án chia thỏa mãn.

Example

Test 1

Input

3
1 2 3 4 5 6 7
2 2 2 2 2 2 2
10 20 30 40 50 60 70

Output

120
-1
1200000

Note

Ở testcase 1: Tổng \(7\) số là \(28\). Ta cần chọn ra \(4\) số có tổng bằng \(14\) sao cho tích lớn nhất. Các bộ \(4\) số thỏa mãn có thể là \(\{2, 3, 4, 5\}\) (tổng = \(14\), tích = \(120\)), \(\{1, 3, 4, 6\}\) (tổng = \(14\), tích = \(72\)), .... Tích lớn nhất đạt được là \(120\).
Ở testcase 2: Tổng của cả \(7\) số là \(14\). Nhóm \(S_1\) gồm \(4\) số luôn có tổng là \(8\), nhóm \(S_2\) gồm \(3\) số luôn có tổng là \(6\). Không bao giờ có thể chia thành hai nhóm có tổng bằng nhau, do đó kết quả là \(-1\).

Bình luận

Tải bình luận...

Không có bình luận nào.