Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Những con bò vừa có một quyết định táo bạo để thoát khỏi nanh vuốt của nông dân John (FJ). Chúng thu xếp để có được một cái bè nhỏ không phẳng và với sự che chở của bóng đêm, một số con bò sẽ lên bè chèo dọc theo con sông tiếp giáp với đồng cỏ. Kế hoạch trông rất hoàn hảo cho tới khi những con bò nhận ra rằng chiếc bè không phẳng không thể chở được quá nhiều cân.

Cả đàn có N con bò có trọng lượng là w₁, w₂, ..., w_N. Để tìm ra một nhóm những con bò đủ nhẹ để tránh vụ chìm bè những con bò lấy tổng các trọng lượng của chúng. Thật không may, bò vốn nổi tiếng về kém số học, cho nên nếu một lần thêm trọng lượng của một con bò gây ra một phép cộng có nhớ (trong cơ số 10) đàn bò sẽ bỏ cuộc và kết luận là nhóm của chúng quá nặng để có thể đi trên bè.

Hãy giúp các con bò tính toán nhóm nhiều bò nhất mà đàn bò tin tưởng có thể chở được trên cái bè (tức là nhóm nhiều bò nhất mà khi trọng lượng của nó được thêm vào tổng thì không có sự cố xảy ra - không phát sinh nhớ)

Dữ liệu: Vào từ file văn bản ESCAPE.INP

• Dòng đầu tiên ghi số lượng các con bò N (1≤N≤20)
• N dòng tiếp theo, mỗi dòng ghi trọng lượng của một con bò là một số nguyên dương không vượt quá 10⁸.

Kết quả: Ghi ra file văn bản ESCAPE.OUT số lượng lớn nhất các con bò mà trọng lượng của chúng khi thêm vào không phát sinh phép cộng có nhớ

Ví dụ: