Bức tường gồm n cột gạch, chiều cao cột thứ i ban đầu bằng hi, chiều cao được đo bằng số viên gạch. Bạn phải khôi phục lại bức tường để tất cả n cột phải có chiều cao bằng nhau

Bạn được phép thực hiện các thao tác sau:

• Đặt một viên gạch lên trên đỉnh một cột, chi phí của thao tác này là a;
• Dỡ một viên gạch khỏi đỉnh một cột không trống, chi phí cho thao tác này là r;
• Di chuyển một viên gạch từ đỉnh một cột không trống này sang đỉnh một cột khác, chi phí cho thao tác này là m.

Bạn không thể tạo thêm cột hoặc bỏ qua cột tồn tại trước đó ngay cả khi chiều cao của nó trở thành 0. Bạn hãy tính tổng chi phí khôi phục tối thiểu, hay nói cách khác là tính tổng chi phí tối thiểu để làm tất cả n cột có chiều cao bằng nhau.

Dữ liệu: Vào từ tệp văn bản rest.inp

• Dòng đầu tiên chứa 4 số nguyên n, a, r , m (1 ≤ n ≤ ~10^5~; 0 ≤ a, r, m ≤ ~10^4~) tương ứng là số cột và chi phí các thao tác đặt, dỡ, di chuyển một viên gạch.
• Dòng thứ hai chứa n số nguyên ~h_1, h_2,..., h_n~ (0 ≤ ~h_i~ ≤ ~10^9~) là độ cao các cột.

Kết quả: Ghi ra tệp văn bản rest.out một số nguyên là chi phí khôi phục tối thiểu.

Ví dụ:

rest.inp

5 1 2 4
5 5 3 6 5

rest.out

4

rest.inp

5 1 2 2
5 5 3 6 5

rest.out

3

Giải thích ví dụ:

Trong ví dụ thứ nhất, một cách khôi phục bức tường với chi phí tối thiểu là:

• Đặt một viên gạch lên đỉnh cột thứ 3, chi phí cho thao tác này là 1. Bây giờ độ cao của các cột là: 5, 5, 4, 6, 5;
• Tiếp tục đặt một viên gạch lên đỉnh cột thứ 3, chi phí cho thao tác này là 1. Bây giờ độ cao của các cột là: 5, 5, 5, 6, 5;
• Dỡ một viên gạch khỏi đỉnh cột thứ 4, chi phí cho thao tác này là 2. Bây giờ độ cao của các cột là: 5, 5, 5, 5, 5;

Sau các thao tác trên, tất cả các cột đều cao bằng nhau và tổng chi phí là 1+1+ 2 = 4.

Trong ví dụ thứ hai, một cách khôi phục bức tường với chi phí tối thiểu là:

• Di chuyển một viên gạch từ đỉnh cột thứ 4 sang đỉnh cột thứ 3, chi phí cho thao tác này là 2. Bây giờ độ cao của các cột là: 5, 5, 4, 5,5;
• Đặt một viên gạch lên đỉnh cột thứ 3, chi phí cho thao tác này là 1. Bây giờ độ cao của các cột là: 5, 5, 5, 5, 5. Sau các thao tác trên, tất cả các cột đều cao bằng nhau và tổng chi phí là 2 + 1 = 3.

Ràng buộc:

• Có 25% số test: a = r và m ≥ a+r;
• 25% số test khác: 1≤ n ≤ ~10^3~ và 0 ≤ ~h_i~ ≤ ~10^4~;
• 25% số test khác: 0 ≤ ~h_i~ ≤ ~10^6~;
• 25% số test còn lại không có thêm ràng buộc nào

Nguồn