Bác Năm thợ sắt của làng có một thanh sắt dài đúng \(N\) mét đang nằm chờ trong xưởng. Khách đến đặt mua sắt theo đoạn: đoạn dài \(i\) mét bác có thể bán với giá \(p_i\) đồng. Bác được phép cắt thanh sắt thành bao nhiêu đoạn nhỏ cũng được, không giới hạn số lượng mỗi loại độ dài, miễn là tổng độ dài các đoạn cắt ra đúng bằng \(N\) và đoạn nào cũng được bán.

Bác muốn tính trước xem với bảng giá đã cho, nên cắt thanh sắt này thành các đoạn như thế nào để thu được nhiều tiền nhất.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(p_1, p_2, \dots, p_N\) (\(1 \le p_i \le 10^9\)).

Định dạng đầu ra

• In ra tổng số tiền lớn nhất bác Năm thu được.

Ví dụ

Input:

8
1 5 8 9 10 17 17 20

Output:

22

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 2000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.