Ivica và tập đoàn (gồm ~N~ công ty anh ấy sỡ hữu) đang gặp khó khăn. Các công ty đang trong tình cảnh nợ nần chồng chất nên các luật sư đang đến để tước các công ty từ anh ấy. May mắn là Ivica đã bàn bạc nhằm giữ lại cho anh ấy một số công ty bất chấp nợ nần.

Các luật sư đã đặt ~N~ tờ giấy kê nợ của các công ty của Ivica trên bàn. Số nợ của công ty thứ nhất được viết trên tờ giấy thứ nhất ~A_1~, nợ của công ty thứ hai được viết trên ~A_2,...~ và nợ của công ty cuối cùng được viết trên tờ giấy ~A_N~. Ivica đã đàm phán để cho anh ấy giữ lại các công ty ~A_L, A_{L+1},...,A_R~, (~L~ và ~R~ thể hiện vị trí của các tờ giấy được đặt trên bàn). May mắn cho Ivica, các luật sư cũng tham nhũng. Họ bắt anh ấy lấy đoạn con những tờ giấy liên tiếp đã được đàm phán trước đó (từ tờ thứ ~L~ tới tờ thứ ~R~), nhưng cho phép anh ấy tráo 2 tờ giấy trên bàn bất kì với một chi phí nhất định (số lượng lần tráo là không giới hạn). Nói rõ hơn, thao tác tráo tờ giấy ở vị trí ~i~ và vị trí ~j~ tốn ~|i-j|~ đồng. Ivica chỉ còn ~K~ đồng trong túi. Anh ấy dùng số tiền đang có để tráo các tờ giấy sao mà tổng số nợ của các công ty của anh còn sở hữu ấy là bé nhất có thể.

Input

Dòng đầu tiên chứa các số nguyên ~N, L, R~ ~(1 \leq L \leq R \leq N \leq 100)~ và ~K~ ~(0 \leq K \leq 10\:000)~.

Dòng thứ hai chứa ~N~ số nguyên ~A_i~ ~(0 \leq A_i \leq 10^6)~.

Output

In ra số nguyên duy nhất thể hiện tổng lượng nợ bé nhất mà Ivica có thể có nếu anh ấy tiêu dùng ~K~ đồng của anh ấy hợp lí.

Ví dụ

Sample input 1

3 2 2 1
1 2 3

Sample output 1

1

Sample input 2

5 2 3 3
21 54 12 2 0

Sample output 2

12

Sample input 3

6 4 6 100
1 2 3 4 5 6

Sample output 3

6

Ràng buộc

• 7 test đầu có ~N \leq 13~ và ~R = N~.
• 6 test sau có ~N \leq 50~ và ~R=N~.
• 6 test sau thỏa ~N \leq 50~.
• 6 test còn lại không có ràng buộc gì thêm.