Cho một dãy gồm ~n~ số nguyên dương phân biệt ~a_1, a_2, ..., a_n~. Xét các số có thể tạo thành bằng cách lấy tổng của một hoặc nhiều phần tử trong dãy. Mỗi phần tử chỉ có thể được sử dụng tối đa một lần trong một tổng.

Hãy viết chương trình tính toán các giá trị sau:

• Số lượng các tổng khác nhau có thể tạo thành.
• Giá trị tổng có thể được tạo thành bằng nhiều cách nhất và số cách tạo thành nó. Nếu có nhiều giá trị như vậy, hãy chọn giá trị lớn nhất trong đó.
• Dãy có tổng bằng giá trị xác định ở trên và có thứ tự từ điển nhỏ nhất (các số sắp xếp tăng dần).

Input

• Dòng 1: Chứa số nguyên ~n~ (~1 < n \le 70~).
• Dòng 2: Chứa ~n~ số nguyên dương phân biệt ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 1000~).

Output

• Dòng 1: Số lượng các tổng khác nhau có thể tạo thành.
• Dòng 2: Hai số nguyên — tổng có nhiều cách tạo thành nhất và số cách tạo thành nó. Dữ liệu đảm bảo số cách tạo thành không vượt quá ~5 \times 10^{18}~.
• Dòng 3: Dãy có tổng trên và có thứ tự từ điển nhỏ nhất (các số sắp xếp tăng dần).

Sample Input

4
1 3 4 6

Sample Output

12
10 2
1 3 6

Giải thích ví dụ

• Có ~12~ tổng có thể tạo thành là: ~1, 3, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15~.
• Các tổng ~4, 7, 10~ đều có thể tạo thành bằng ~2~ cách. Tổng lớn nhất trong đó là ~10 = 1 + 3 + 6~ hoặc ~10 = 4 + 6~. Bài yêu cầu chọn cách có thứ tự từ điển nhỏ nhất là ~1, 3, 6~.

Subtasks