Cho mảng số nguyên \(a\) gồm \(N\) phần tử và một số nguyên dương \(K\). Với mỗi cửa sổ trượt kích thước \(K\) di chuyển từ trái sang phải, hãy tính tổng của phần tử lớn nhất và phần tử nhỏ nhất trong cửa sổ đó. Sau đó, tính tổng của tất cả các giá trị thu được từ mỗi cửa sổ và in ra kết quả.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le K \le N \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) cách nhau bởi dấu cách (\(-10^9 \le a_i \le 10^9\)).

Định dạng đầu ra

• Một số nguyên duy nhất là tổng của các giá trị (Lớn nhất + Nhỏ nhất) trên tất cả các cửa sổ trượt.

Ví dụ

Input:

5 3
2 5 -1 7 -3

Output:

14

Giải thích

• Cửa sổ \(\{2, 5, -1\}\): max = 5, min = -1. Tổng = 4.
• Cửa sổ \(\{5, -1, 7\}\): max = 7, min = -1. Tổng = 6.
• Cửa sổ \(\{-1, 7, -3\}\): max = 7, min = -3. Tổng = 4.
• Tổng cộng: \(4 + 6 + 4 = 14\).

Ràng buộc

• 30% số điểm ứng với \(N \le 1000\).
• 70% số điểm còn lại không có ràng buộc gì thêm.
• Kết quả có thể vượt quá giới hạn số nguyên 32-bit.