Đề bài

Sau thương vụ bản quyền phát sóng ~WC~ 2018, để tăng thêm uy tín, đồng thời quảng bá thêm hình ảnh, đài truyền hình ~ATA~ muốn lắp đặt thêm ~k~ màn hình ~LED~ (SMD và DIP) cỡ lớn để phục vụ người dân xem ~ASIAD~ tại các trạm nghỉ khác nhau trên quốc lộ từ ~HN~ tới ~SG~.

Qua khảo sát, có tất cả ~n~ trạm nghỉ, trạm nghỉ thứ ~i~ cách ~HN~ ~d_i~ km. Vì trục đường dài nên các màn hình phải thỏa mãn điều kiện là khoảng cách giữa hai màn hình liền tiếp trên đường, cũng như khoảng cách từ ~HN~ hoặc ~SG~ tới màn hình gần nhất phải không nhỏ hơn ~L~ km và không lớn hơn ~R~ km.

Màn hình thứ ~i~ được xây dựng có một hệ số hiệu quả ~T_i~ là tổng các khoảng cách từ quán đó đến những quán còn lại. ~T_i~ càng lớn thì giá trị phục vụ của quán đó càng cao. Vấn đề đặt ra là phải chọn ra ~k~ điểm sao cho tổng các ~T_i~ (giá trị phục vụ chung) là lớn nhất.

Yêu cầu: Cho ~n, k~, khoảng cách giữa ~HN~ và các trạm nghỉ, khoảng cách từ ~HN~ tới ~SG~. Hãy xác định giá trị phục vụ chung lớn nhất có thể đạt được. Dữ liệu đảm bảo có phương án.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq k \leq n \leq 5000)~.
• Dòng thứ hai chứa ~2~ số ~L~ và ~R~ ~(1 \leq L \leq R \leq 10^9)~.
• Dòng thứ ba chứa số nguyên dương không vượt quá ~10^9~ là khoảng cách giữa ~HN~ và ~SG~.
• Dòng thứ tư chứa ~n~ số nguyên, số thứ ~i~ xác định khoảng cách từ ~HN~ tới trạm nghỉ thứ ~i~, các số được đưa theo thứ tự tăng dần, không có hai trạm nghỉ nào cùng một địa điểm.

Output

• In ra một số nguyên — giá trị phục vụ chung lớn nhất.

Ví dụ

Sample Input

5 3
20 70
195
30 70 90 135 170

Sample Output

420

Giải thích ví dụ

Đặt ~3~ vị trí ~1, 3, 4~ ~(30, 90, 135)~ với hệ số hiệu quả:

~(90 - 30) + (135 - 30) + (90 - 30) + (135 - 90) + (135 - 30) + (135 - 90) = 420~

Giới hạn

• Thời gian: ~1.0s~
• Bộ nhớ: ~256MB~

Nguồn: Idol Nguyễn Văn Híu