Bí mật của kho báu số

Trong một vương quốc cổ đại, có một kho báu vô giá được bảo vệ bởi một câu đố số học phức tạp. Kho báu được chia thành nhiều phần, mỗi phần có một giá trị tương ứng với các số nguyên dương \(a_1, a_2, \ldots, a_n\). Để mở được kho báu, người giải đố phải tìm ra một lượng vàng nhỏ nhất mà không thể tạo ra bằng bất kỳ cách nào kết hợp các phần vàng đã cho, mỗi phần chỉ được sử dụng một lần.

Vị vua thông thái đã đặt ra câu đố này để thử thách trí tuệ của các nhà toán học khắp vương quốc. Ai giải được câu đố sẽ trở thành người giàu có nhất và được tôn vinh.

Bạn có muốn thử sức với câu đố này không? Hãy tìm ra số vàng bí ẩn để mở kho báu và trở thành người chiến thắng!

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 20)\) biểu thị số lượng phần tử của dãy.
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) \((1 \leq a_i \leq 10^9)\) biểu thị các phần tử của dãy.

Output

• In ra một dòng duy nhất chứa số nguyên dương là kết quả của bài toán.

Example

4
1 2 3 6

13

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n = 2\).
• \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 10\) và \(a_i \leq 100\).
• \(40\%\) số test tương ứng với \(30\%\) số điểm không có ràng buộc gì thêm.