Trong chuyến thăm Vương quốc Kẹo ngọt, Alice muốn tham gia thử thách của Quốc vương để mang về những túi quà đầy ý nghĩa. Nội dung của thử thách nghe qua rất đơn giản: Cho một số túi kẹo đặt thành hàng ngang với thông tin số lượng viên kẹo có trong mỗi túi. Alice sẽ được phép lấy lần lượt các túi kẹo (với số lượng túi được chỉ định trước) và trong mỗi lượt chỉ được chọn lấy một trong hai túi kẹo ở hai đầu.

Cho trước thông tin về số lượng kẹo trong các túi và số lượng túi kẹo Alice được lấy. Hãy xác định xem bạn ấy có thể lấy được nhiều nhất bao nhiêu cái kẹo.

Input Specification

Gồm ba dòng:

• Dòng đầu tiên chứa số nguyên dương \(n\), tương ứng là số lượng túi kẹo của Quốc vương;
• Dòng thứ hai chứa \(n\) số nguyên dương, tương ứng là số viên kẹo có trong mỗi túi (theo thứ tự trong hàng);
• Dòng thứ ba chứa số nguyên dương \(l \leq n\), là số túi kẹo mà Alice được lấy.

Output Specification

In ra kết quả trên một dòng.

Constraints

• \(1 \leq l \leq n \leq 10^6\)
• Mỗi túi đựng không quá 1000 viên kẹo

Input Sample 1

7
1 2 3 4 5 6 1
3

Output Sample 1

12

Explanation for Sample Output 1

Alice luôn lấy được 1 viên kẹo ở lượt đầu tiên. Bạn ấy nên chọn lấy ở bên trái để có thể tiếp tục lấy các túi đựng 5 và 6 viên kẹo ở hai lượt sau đó.

Input Sample 2

7
1 2 3 4 5 6 1
7

Output Sample 2

22

Explanation for Sample Output 2

Alice lấy hết toàn bộ số kẹo trong các túi.