Cho ~n~ số nguyên dương ~a_i,i=1..n~, bạn phải đặt giữa ~n~ số nguyên dương này ~2~ phép nhân và ~n-3~ phép cộng sao cho kết quả biểu thức là lớn nhất.

Ví dụ: với ~n=5~ và dãy ~a_i~ là ~4, 7, 1, 5, 3~ thì bạn có thể có các biểu thức:

• ~4 + 71 + 53~;
• ~471 + 5 + 3~.

Chú ý: Không được thay đổi thứ tự xuất hiện của ~a_i,i=1..n~ trong biểu thức thu được.

Input

• Dòng đầu chứa số nguyên dương ~n\ (4≤n≤1000)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~a_i\ (1≤a_i≤10000,i=1..n)~.

Output

• Ghi ra một số nguyên dương duy nhất là giá trị lớn nhất của biểu thức thu được.

Sample

Input #1

5
4
7
1
5
3

Output #1

44

Hint

• Biểu thức thu được là: ~47 + 1 + 53~.

Problem source: Chuyên Sơn La Online Judge