Một thanh sắt có độ dài ~l~ có thể được cắt thành các đoạn nhỏ hơn.

Cho bảng giá gồm ~l~ số nguyên dương ~p_1,p_2,...,p_l~, trong đó ~p_i~ là giá bán của một đoạn sắt có độ dài ~i~.

Bạn có thể cắt hoặc không cắt thanh sắt, và có thể sử dụng lại cùng một độ dài nhiều lần (tức là có thể cắt ra nhiều đoạn cùng độ dài).

Yêu cầu: Hãy xác định cách cắt thanh sắt sao cho tổng giá trị thu được là lớn nhất.

Input

• Dòng thứ nhất: một số nguyên dương ~l~ (~1 \leq l \leq 10^6~).
• Dòng thứ hai: gồm ~l~ số nguyên dương ~p_1,p_2,...,p_l~ (~1 \leq p_i \leq l~).

Output

Một số nguyên duy nhất — giá trị thu được lớn nhất khi cắt thanh sắt tối ưu.

Example input 1

5
2 5 7 3 9

Example output 1

12

Note 1

• Có thể cắt thanh sắt dài 5 thành các đoạn dài 2 và 3, thu được tổng giá ~p_2+p_3 = 5+7=12~, là lớn nhất.