Bài tập

Con đường từ trường về nhà bạn Huy dài \(X\) km. Huy muốn trồng hoa tử đằng dọc đường: mỗi hố trồng chiếm \(Y\) mét chiều dài, và khoảng cách giữa hai hố liền kề, cũng như từ đầu đường đến hố đầu tiên và từ hố cuối cùng đến cuối đường, đều phải ít nhất \(Z\) mét.

Tính số cây nhiều nhất Huy có thể trồng (có thể là \(0\)).

Input

Một dòng chứa ba số nguyên dương \(X, Y, Z\).

Output

In ra số cây tối đa trồng được.

Constraints

• \(1 \le X, Y, Z \le 2^{31}\)
• Đổi đơn vị: \(1\) km \(= 1000\) m.

Sample Input

3 200 100

Sample Output

9

Explanation

Đường dài \(3000\) m. Với \(9\) cây cần \(9 \cdot 200 + 10 \cdot 100 = 2800 \le 3000\) m, còn \(10\) cây cần \(3100 > 3000\) m.

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Trang trại có hai máy vắt sữa. Mỗi con bò phải được đưa vào đúng một trong hai máy, và để hai máy chạy công suất như nhau, tổng lượng sữa của các con bò ở máy 1 phải bằng tổng lượng sữa của các con bò ở máy 2.

Một cách xếp là dãy \(x_1 x_2 \dots x_n\) với \(x_i \in \{1, 2\}\), trong đó \(x_i\) là số hiệu máy dành cho con bò thứ \(i\). Hãy liệt kê tất cả các cách xếp thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Nếu không có cách xếp nào, in ra -1.
• Ngược lại, mỗi dòng in một cách xếp dưới dạng xâu \(n\) chữ số \(x_1 x_2 \dots x_n\) viết liền nhau (không có dấu cách). Các cách xếp được in theo thứ tự từ điển tăng dần (so sánh như xâu ký tự).

Constraints

• \(1 \le n \le 20\)
• \(1 \le a_i \le 10^9\)

Sample Input

5
1 3 2 2 4

Sample Output

11122
11212
22121
22211

Explanation

Tổng sữa là \(12\), mỗi máy phải vắt được \(6\). Chẳng hạn cách 11122: máy 1 nhận các con \(1,2,3\) (\(1+3+2=6\)), máy 2 nhận các con \(4,5\) (\(2+4=6\)).

Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày, và hai chuồng bò. Mỗi con bò được nhốt vào chuồng thứ nhất, chuồng thứ hai hoặc không được nhốt vào chuồng nào. Yêu cầu: tổng lượng sữa của chuồng thứ nhất bằng tổng lượng sữa của chuồng thứ hai. Bò không có chuồng sẽ không cho sữa nữa.

Sắn muốn tổng lượng sữa thu được (của cả hai chuồng cộng lại) là lớn nhất có thể.

Hãy tìm lượng sữa lớn nhất đó, đồng thời liệt kê mọi tập bò bị bỏ ngoài chuồng mà vẫn đạt được lượng sữa lớn nhất (hai cách chia khác nhau nhưng có cùng tập bò bị bỏ ngoài chỉ được tính một lần). Cho phép để trống cả hai chuồng.

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

• Dòng đầu tiên: lượng sữa lớn nhất thu được.
• Các dòng tiếp theo: mỗi dòng là một tập bò bị bỏ ngoài chuồng (liệt kê số thứ tự các con bò theo thứ tự tăng dần, cách nhau một dấu cách). Các tập được in theo thứ tự từ điển tăng dần (so sánh từng số nguyên, dãy ngắn hơn là tiền tố của dãy dài hơn thì đứng trước).
• Nếu tất cả bò đều được nhốt vào chuồng thì chỉ in đúng một dòng OK thay cho danh sách tập.
• Nếu không thể nhốt con nào (lượng sữa lớn nhất là \(0\)) thì tập bò bị bỏ ngoài chỉ có một, gồm tất cả các con bò.

Constraints

• \(1 \le n \le 15\)
• \(1 \le a_i \le 10^9\)

Sample Input 1

7
4 6 10 3 7 5 2

Sample Output 1

34
4

Sample Input 2

6
2 3 3 5 9 4

Sample Output 2

26
OK

Explanation

Ở ví dụ 1 tổng sữa là \(37\) (lẻ) nên phải bỏ ra ít nhất một con; bỏ con thứ \(4\) (\(3\) đơn vị) còn lại \(34\), chia được thành hai chuồng \(17 + 17\) (ví dụ \(4+6+7\) và \(10+5+2\)). Ở ví dụ 2 cả sáu con đều nhốt được: \(2+3+3+5 = 13 = 9+4\).

Trang trại của Sắn có \(n\) con bò sữa, con thứ \(i\) cho \(a_i\) đơn vị sữa mỗi ngày. Sắn vừa xây hai chuồng bò mới và muốn nhốt bò vào hai chuồng sao cho tổng lượng sữa của các con bò trong chuồng thứ nhất bằng tổng lượng sữa của các con bò trong chuồng thứ hai. Mỗi con bò được nhốt vào tối đa một chuồng; những con bò không được nhốt vào chuồng nào coi như bị "thừa".

Sắn không muốn bỏ phí con bò nào nên muốn số con bò bị thừa là ít nhất. Hãy tính số con bò thừa tối thiểu. (Cho phép để trống cả hai chuồng, khi đó tổng của hai chuồng cùng bằng \(0\) và mọi con bò đều thừa.)

Input

• Dòng đầu tiên gồm số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\).

Output

In ra một số nguyên duy nhất là số con bò thừa tối thiểu.

Constraints

• \(1 \le n \le 15\)
• \(1 \le a_i \le 10^9\)

Sample Input

7
10 4 6 3 3 9 12

Sample Output

1

Explanation

Tổng lượng sữa là \(47\) (số lẻ) nên chắc chắn phải bỏ ra ít nhất một con. Bỏ con thứ \(6\) (\(9\) đơn vị) ta còn \(38\), chia được thành chuồng một gồm các con \(10, 3, 6\) và chuồng hai gồm \(12, 4, 3\) với cùng tổng \(19\).