Những thời kỳ khó khăn đang chờ đợi Ivica và Tập đoàn của ông – một nhóm gồm ~N~ công ty Croatia thuộc sở hữu của ông. Mỗi công ty này đều đang mắc nợ, vì vậy nhà nước đã cử luật sư đến để tịch thu tất cả tài sản của ông. Chúng tôi đã tìm hiểu được rằng Ivica đã đạt được thỏa thuận với nhà nước để giữ lại một số công ty bất chấp khoản nợ lớn. Những công ty nào? Chúng tôi cũng đã tìm ra điều đó.

Các luật sư nhà nước đã đặt ~N~ tờ giấy chứng nhận quyền sở hữu của các công ty của Ivica trên bàn. Khoản nợ của công ty đầu tiên được ghi trên tờ giấy đầu tiên là ~A_1~, khoản nợ của công ty thứ hai được ghi trên ~A_2, ...~ và khoản nợ của công ty cuối cùng được ghi trên tờ giấy cuối cùng là ~A_N~. Ivica đã thỏa thuận với nhà nước để giữ lại các công ty từ ~A_L, A_{L+1}, ..., A_R~ thuộc quyền sở hữu của mình, trong đó ~L~ và ~R~ đại diện cho vị trí trong mảng giấy trên bàn.

May mắn cho Ivica, các luật sư cũng tham nhũng. Họ sẽ buộc ông phải lấy cùng một mảng con liên tiếp như đã thỏa thuận (từ tờ giấy thứ ~L~ đến tờ giấy thứ ~R~), nhưng họ sẽ để ông đổi chỗ bất kỳ hai tờ giấy nào trên bàn với một chi phí cụ thể. Cụ thể, đổi chỗ các tờ giấy tại vị trí ~i~ và ~j~ sẽ tốn của ông ~|i − j|~ kuna (đơn vị tiền tệ của Croatia). Ivica đang rất tuyệt vọng. Ông chỉ có ~K~ kuna trong túi và ông muốn sử dụng chúng sao cho tổng số nợ của các công ty mà ông giữ lại là nhỏ nhất có thể.

Hãy giúp Ivica đạt được mục tiêu của mình.

Input

• Dòng đầu tiên chứa bốn số nguyên cách nhau bởi dấu cách là ~N, L, R~ ~(1 \leq L \leq R \leq N \leq 100)~ và ~K~ ~(0 \leq K \leq 10.000)~ từ mô tả bài toán.
• Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(0 \leq A_i \leq 10^6)~ từ mô tả bài toán.

Output

Bạn nên xuất ra một số nguyên duy nhất đại diện cho số nợ nhỏ nhất mà Ivica sẽ có nếu ông sử dụng ~K~ kuna một cách tối ưu.

Chú ý

• Nhóm 1 (22 điểm): ~N ≤ 13~ và ~R = N~.
• Nhóm 2 (33 điểm): ~N ≤ 50~ và ~R = N~.
• Nhóm 3 (33 điểm): ~N ≤ 50~.
• Nhóm 4 (22 điểm): Không có ràng buộc bổ sung.

Sample Input 1

3 2 2 1
1 2 3

Sample Ouput 1

1

Sample Input 2

5 2 3 3
21 54 12 2 0

Sample Ouput 2

12

Sample Input 3

6 4 6 100
1 2 3 4 5 6

Sample Ouput 3

6