An có một vườn cây rộng lớn trồng nhiều loại cây khác nhau, mỗi loại cây được trồng theo hàng. Năm nay, trong vườn cây của An có một hàng cây đã đến tuổi thu hoạch. Hàng cây này gồm có ~ N ~ cây được đánh số thứ tự từ 1 đến ~ N ~, cây thứ ~ i (1≤i≤N) ~ được định giá là ~ a_i ~ đồng.

An không muốn bán hết ~ N ~ cây mà muốn giữ lại một đoạn liên tiếp các cây từ vị trí ~ L ~ đến vị trí ~ R ~ để vườn cây vẫn giữ được độ thẩm mỹ cao. Mặt khác, An muốn các cây bán đi phải thu được lợi nhuận lớn nhất có thể. An đã thuê công nhân chuyển vị trí hai cây bất kì trong hàng cây với chi phí nhất định. Cụ thể, nếu chuyển vị trí cây thứ ~ i ~ và cây thứ ~ j ~ cho nhau thì mất chi phí chuyển là ~ |i-j| ~ đồng.

Hiện tại, An chỉ có ~ K ~ đồng dùng để thuê công nhân chuyển vị trí các cây.

Yêu cầu: Bạn hãy giúp An viết chương trình tính số tiền lớn nhất thu được khi bán cây. Sao cho, An vẫn giữ lại được các cây từ vị trí ~ L ~ đến vị trí ~ R ~ mà chỉ dùng không quá ~ K ~ đồng tiền thuê chuyển cây?

Dữ liệu vào:

• Dòng đầu tiên chứa bốn số nguyên ~ N, L, R, K (1≤L≤R≤N≤100;0≤K≤10^6) ~.
• Dòng thứ hai chứa ~N~ số nguyên ~ a_i (0≤a_i≤10^6, i=1,2,…,N) ~ lần lượt là giá trị các cây trong hàng.

Kết quả:

• Một số nguyên duy nhất là số tiền lớn nhất An thu được khi bán cây.

Ví dụ:

Input

3 2 2 1
1 2 3 

Output

5 

Giải thích

• Chuyển cây vị trí 1 và 2 tốn chi phí 1.
• Giữ lại cây vị trí 2 và chi phí bán cây thu được là 5.

Ràng buộc:

• Có 30% số test ứng với 30% số điểm có ~ N≤10, R=N ~.
• 30% số test ứng với 30% số điểm có ~ R = N, K≤10^4 ~.
• 20% số test ứng với 20% số điểm có ~ K<=10^4 ~
• 20% số test ứng với 20% số điểm không có giới hạn nào thêm.