Một công ty sản xuất nội thất có \(n\) đội, đội thứ \(i\) đang cần các đoạn gỗ độ dài \(a_i\) để lắp ghép. Công ty sẽ đặt hàng các thanh gỗ dài cùng kích thước để có thể phù hợp với tất cả các đội.

Thanh gỗ dài phù hợp với đội \(i\) nếu có thể cắt thanh gỗ dài đó thành các đoạn có độ dài bằng \(a_i\) để sử dụng mà không thừa bất cứ khúc nào. Để dễ dàng vận chuyển, giám đốc công ty muốn độ dài thanh gỗ đặt hàng về là ngắn nhất có thể.

Yêu cầu: Cho biết \(n\) và các giá trị \(a_1, a_2, \dots, a_n\). Hãy tính độ dài ngắn nhất của thanh gỗ phù hợp với tất cả các đội được công ty đặt hàng về.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(2 \le n \le 6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 1000\) với mọi \(i = 1, 2, \dots, n\)).

Output

• Một số nguyên duy nhất là độ dài thanh gỗ ngắn nhất tìm được.

Example

2
5 6

30

3
2 10 4

20

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n = 2\) và \(a_i \le 2\).
• Subtask \(2\) (\(40\%\) số điểm): \(n \le 3\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc bổ sung.