#1478. BONUS - Phần thưởng

Hồng là người thắng cuộc trong cuộc thi “Xây dựng Hệ thống chống dịch COVID-19” và được nhận phần thưởng của Ban tô chức. Ban tổ chức chuẩn bị một bảng kích thước . Các dòng của bảng được đánh số từ đến , từ trên xuống dưới. Các cột của bảng được đánh số từ đến , từ trái qua phải. Ô nằm trên giao của dòng và cột được gọi là ô và trên ô đó ghi một số nguyên có giá trị .

Để nhận phần thưởng Hồng được phép chọn một dãy gồm ít nhất ba ô thỏa mãn:

• Độ dài đoạn thẳng nối giữa tâm của hai ô và nhỏ hơn độ dài đoạn thắng nói giữa tâm của hai ô Và với mọi ;
• Gọi là tổng tất cả các số trong các ô của dãy, số tiền mà Hồng nhận được là giá trị tuyệt đối của . Các ô của dãy có thê được lặp lại và đương nhiên sẽ được tính tổng mỗi lần lặp lại.

Yêu cầu: Hãy giúp Hồng tính giá trị lớn nhất có thể.

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên dương ;
• Dòng thứ trong dòng tiếp theo chứa số nguyên .

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là giá trị lớn nhất có thể chọn được.

Ví dụ:

Dữ liệu vào:

1 4 
-1 2 3 4 

Dữ liệu ra:

10

Giải thích:

• Các ô được chọn .

Giới hạn:

• Có số test ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test khác ứng với số điểm của bài có ;
• Có số test còn lại ứng với số điểm của bài có .