(coupon.*)

Trong ngày sinh nhật, Po được các bạn tặng \(k\) phiếu giảm giá mua hàng ở cửa hàng Thế giới ô tô. Khi sử dụng một phiếu giảm giá, Po được giảm \(x\) đồng, Po có thể áp dụng nhiều phiếu giảm giá khi mua một mặt hàng. Nếu Po áp dụng \(t\) phiếu giảm giá khi mua một mặt hàng có giá \(y\) đồng thì số tiền mà Po phải trả khi mua mặt hàng đó là \(max(y - t \times x,0)\);

Ví dụ 1: Po áp dụng 2 phiếu giảm giá, mỗi phiếu được giảm 4 đồng khi mua một mặt hàng có giá 10 đồng thì số tiền Po phải trả cho mặt hàng đó là \(\max(10 - 2 \times 4,\ 0) = 2\) đồng.

Ví dụ 2: Po áp dụng 4 phiếu giảm giá, mỗi phiếu được giảm 5 đồng khi mua một mặt hàng có giá 16 đồng thì số tiền Po phải trả cho mặt hàng đó là \(\max(16 - 4 \times 5,\ 0) = 0\) đồng.

Cho biết Po mua \(n\) mặt hàng, các mặt hàng có giá lần lượt là \(a_{1},a_{2},\ldots,a_{n}\). Hãy giúp Po xác định số tiền ít nhất mà Po cần thanh toán sau khi áp dụng \(k\) phiếu giảm giá?

Dữ liệu vào:

+ Dòng đầu tiên ghi 3 số nguyên dương \(n,\ k,\ x\) lần lượt cho biết số lượng mặt hàng Po cần mua, số phiếu giảm giá và số tiền được giảm khi áp dụng 1 phiếu giảm giá.

+ Dòng thứ hai ghi lần lượt các số nguyên \(a_{1},a_{2},\ldots,a_{n}\) cho biết giá của \(n\) hàng.

Kết quả:

+ Ghi một số nguyên cho biết số tiền ít nhất Po cần trả khi áp dụng \(k\) phiếu giảm giá để mua \(n\) mặt hàng.

Ví dụ:

Giải thích ví dụ:

+ KHÔNG áp dụng phiếu giảm giá vào các mặt hàng có giá 1 và 3;

+ Áp dụng 2 phiếu vào mặt hàng có giá 10 \(\rightarrow\) số tiền phải trả là: \(\max(10 - 2 \times 6,0) = 0\)

+ Áp dụng 1 phiếu vào mặt hàng có giá 7 \(\rightarrow\) số tiền phải trả là: \(\max(7 - 1 \times 6,0) = 1\)

+ Áp dụng 1 phiếu vào mặt hàng có giá 5 \(\rightarrow\) số tiền phải trả là: \(\max(5 - 1 \times 6,0) = 0\)

Như vậy tổng số tiền phải trả là: 1 + 3 + 0 + 1 + 0 = 5

Ràng buộc:

+ Có 70% số test tương ứng 70% số điểm có \(n \leq 2000\);

+ Có 30% số test còn lại tương ứng 30% số điểm có \(n \leq 10^{5}\).