Những chú bò đã vạch ra một kế hoạch táo bạo để thoát khỏi sự kiểm soát của Nông dân John. Chúng đã xoay xở kiếm được một chiếc bè bơm hơi nhỏ; dưới màn đêm che phủ, một nhóm bò sẽ lên bè và chèo qua con sông giáp với trang trại. Kế hoạch có vẻ hoàn hảo, cho đến khi những chú bò nhận ra rằng chiếc bè bơm hơi nhỏ của chúng có thể không chịu được nhiều trọng lượng!

\(N\) chú bò (\(1 \le N \le 20\)) có trọng lượng \(w_1, \ldots, w_N\). Để xác định một nhóm bò có đủ nhẹ để bè không bị chìm hay không, những chú bò cộng tất cả trọng lượng trong nhóm lại. Đáng tiếc là bò vốn nổi tiếng tính toán kém; nếu phép cộng trọng lượng của các chú bò trong một nhóm phát sinh bất kỳ lần nhớ nào (theo phép cộng thập phân thông thường), chúng sẽ bỏ cuộc và kết luận rằng nhóm đó hẳn quá nặng để dùng bè. Mọi nhóm có thể cộng các trọng lượng mà không phát sinh lần nhớ nào đều được coi là đủ nhẹ để lên bè.

Hãy giúp những chú bò xác định kích thước của nhóm lớn nhất mà chúng tin rằng có thể lên bè (tức là nhóm lớn nhất có thể cộng các trọng lượng mà không phát sinh lần nhớ nào).

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bò \(N\) (\(1 \le N \le 20\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa trọng lượng của một chú bò, là một số nguyên trong đoạn từ \(1\) đến \(100\,000\,000\).

Dữ liệu ra

• Dòng đầu tiên chứa số lượng bò trong nhóm lớn nhất có thể cộng các trọng lượng mà không phát sinh lần nhớ nào.

Ví dụ

5
522
6
84
7311
19

3

   522
     6

+ 7311
------
  7839

Nguồn

USACO 2011 December Contest, Bronze Division — Escaping the Farm

Tác giả đề: Brian Dean và Kalki Seksaria, 2011.