Alice vừa đoạt giải quán quân trong một kỳ thi lập trình danh giá. Ban tổ chức trao thưởng thông qua một trò chơi như sau: Có thẻ xếp trên một hàng dài, trên mỗi thẻ xếp một số nguyên dương. Ban tổ chức cho Alice thực hiện nhiều bước để chọn ra đúng cặp thẻ , mỗi bước thực hiện theo một trong các quy tắc sau:
Chọn hai thẻ đầu hàng;
Chọn hai thẻ cuối hàng;
Chọn một thẻ đầu hàng và một thẻ cuối hàng;
Loại một thẻ đầu hàng ra khỏi hàng;
Loại một thẻ cuối hàng ra khỏi hàng.
Sau mối bước, nếu chọn được hai thẻ thì loại hai thẻ đó ra khỏi hàng và Alice nhận được số tiền thưởng bằng giá trị tuyệt đối của hiệu hai số ghi trên hai thẻ đó.
Yêu cầu: Hãy giúp Alice tìm cách chơi chọn đúng cặp thẻ để đạt được tổng số tiền thưởng là lớn nhất.
Dữ liệu vào:
Dòng thứ nhất chứa hai số nguyên dương và ;
Dòng thứ hai chứa số nguyên dương là giá trị ghi trên từng thẻ, mỗi thẻ một số tương ứng lần lượt từ đầu hàng. Các số có giá trị không vượt quá .
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là tổng tiền thưởng lớn nhất tìm được.
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: ;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
Ví dụ:
Dữ liệu vào:
6 2
1 3 10 2 1 4
Dữ liệu ra:
12
Giải thích:
Bước : Alice chọn hai thẻ cuối hàng là và và nhận được số tiền thưởng là ;
Bước : Alice loại thẻ cuối hàng có giá trị ;
Bước : Alice chọn một thẻ đầu hàng và một thẻ cuối hàng có giá trị là và và nhận được số tiền thưởng là ;
Tổng tiền thưởng Alice nhận được là .
