Giải bài trực tuyến

Để phát triển ngành công nghệ thông tin của vương quốc C11, virtuspro94 đang lên kế hoạch tuyển chọn lại đội ngũ lập trình viên tài năng. Và lần này, anh đã quyết định đưa ra một bài toán khó để kiểm tra năng lực các coders ở vương quốc của mình. Bài toán được virtuspro94 đưa ra như sau :

Cho dãy N số nguyên có giá trị thuộc khoảng [-10⁶, 10⁶]. Bạn được phép chọn một bảng ô vuông bất kì thỏa mãn :

• H x W = N (với H là chiều cao của bảng và W là chiều rộng của bảng)
• Min(H, W) >= 2

Với bảng bạn đã chọn, lần lượt điền các số A₁, A₂, .. , A_N từ trái sang phải, trên xuống dưới, nói cách khác các số A₁, A₂, .. , A_N lần lượt được điền vào các ô (1, 1), (1, 2), .. , (1, W), (2, 1), (2, 2), … , (2, W), … , (H, 1), (H, 2), … (H, W). Tiếp đó, bạn sẽ chọn một số ô trong bảng và điểm bạn nhận được chính là tổng các số trên tất cả các ô bạn chọn. Nhưng nếu chỉ có thế thì thực sự quá dễ dàng với trình độ các coders của C11 để đạt được số điểm tốt nhất, nên virtuspro94 đã đưa ra 1 điều kiện oái oăm :

• Với mọi hình vuông 2 x 2, bạn phải chọn ít nhất 1 ô nhưng đồng thời cũng không được chọn hết cả 4 ô.
  

Bài toán giờ đã trở nên khá là “dị”. Nhưng bạn là một coder giỏi, hãy thể hiện khả năng của mình bằng việc tìm ra số điểm lớn nhất bạn có thể đạt được là bao nhiêu?

Input

• Dòng đầu là số N <= 200 và thỏa mãn có ít nhất 1 bảng ô vuông thỏa mãn điều kiện đề bài.
• Dòng tiếp theo là dãy N số, mỗi số cách nhau 1 dấu cách.

Output

• 1 dòng duy nhất là số điểm lớn nhất bạn có thể đạt được.

Example

Input:
4

2 3 -1 2

Output:
7