Dãy số

Cho một dãy gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ và các số nguyên $b, k_1, k_2$. Bạn được thực hiện tối đa $k_1 + k_2$ phép toán trên các phần tử của dãy để giảm tổng các phần tử của dãy số đã cho.

• Phép toán loại 1: Chọn một số $a_i$ bất kì của dãy và thay thế số $a_i$ bằng số $\left[\frac{a_i}{2}\right]$ (chia đôi và lấy phần nguyên, ví dụ $\left[\frac{17}{2}\right] = 8$). Bạn được sử dụng tối đa $k_1$ phép toán loại 1.
• Phép toán loại 2: Chọn một số $a_i$ bất kì của dãy và thay thế $a_i$ bằng giá trị lớn nhất của hai số $a_i - b$ và $0$ (trừ đi $b$ đơn vị, nếu kết quả âm thì lấy bằng $0$). Bạn được sử dụng tối đa $k_2$ phép toán loại 2.

Quy tắc: Với mỗi số $a_i$ trong dãy, bạn có thể chọn: không phép toán nào, chỉ phép toán loại 1, chỉ phép toán loại 2, hoặc dùng cả hai phép toán, mỗi phép toán được thực hiện tối đa 1 lần với số $a_i$. Nếu dùng cả hai loại trên cùng một số, bạn có thể thực hiện theo thứ tự tùy ý.

Yêu cầu: Hãy tìm tổng nhỏ nhất của dãy số sau khi sử dụng tối đa $k_1$ phép toán loại 1 và $k_2$ phép toán loại 2.

Từ tệp văn bản arr.inp,

• Dòng đầu chứa 4 số nguyên $n, b, k_1, k_2$ ($1 \le n \le 300$; $1 \le b \le 10^9$; $0 \le k_1, k_2 \le n$);
• Dòng thứ hai chứa $n$ số nguyên dương $a_i$ ($1 \le a_i \le 10^9$).

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách.

Ghi ra tệp văn bản arr.out,

• Một số nguyên duy nhất là tổng nhỏ nhất tìm được.

• Ràng buộc 1: 30% số test ứng với 30% số điểm của bài có $k_2 = 0$;
• Ràng buộc 2: 30% số test ứng với 30% số điểm của bài có $a_1 = a_2 = \ldots = a_n$;
• Ràng buộc 3: 40% số test ứng với 40% số điểm của bài có $n, k_1, k_2 \le 300$, các giá trị đầu vào khác không có ràng buộc gì thêm.