Lâu đài cát
View as PDFCTN vừa xây xong ~1~ lâu đài bằng cát! Cũng giống như tất cả các lâu đài khác, trên đỉnh những bức tường, sẽ có những lỗ trống (để đặt đại bác cho việc phòng thù chẳng hạn), và về hai phía của lỗ trống -- tất nhiên sẽ có ~2~ vùng cao hơn. Tạm gọi các vùng cao hơn này là Merlons. Lâu đài có ~N~ ~(1 \le n \le 25000)~ Merlons, để thuận tiện ta đánh số chúng từ ~1 \rightarrow N~; Merlon thứ ~i~ có chiều cao ~M_i~ ~(1 \le M_i \le 100 000)~;
Ngài CTN muốn sửa chữa lâu đài thành một mẫu mới, anh ta đã làm một danh sách ~N~ số nguyên ~B_1, \dots, B_N~ ~(1 \le B_i \le 100000)~, và anh muốn thay đổi chiều cao của các Merlon từ ~(A_1, \dots, A_n)~ thành ~(B_1, \dots B_n)~ theo một thứ tự nào đó.
Để làm được điều này, anh ta đã thuê một số kỹ sư để thiết kế những Merlon theo ý muốn của mình. Tất nhiên chi phí cho việc này là rất đắt đỏ. Theo tính toán sơ bộ thì:
- Chi phí để tăng chiều cao của một đơn vị là ~X~
- Chi phí để giảm chiều cao của một đơn vị là ~Y~
Hãy giúp CTN tìm ra phương án để có được bức tường mới mà giá phải trả là nhỏ nhất!
Input
Dòng đầu: ~3~ số ~N, X, Y~ cách nhau ít nhất ~1~ dấu cách
Dòng ~2~ ...~N + 1~: mỗi dòng là ~2~ số ~A_i, B_i~ cách nhau ít nhất ~1~ dấu cách
Output
Gồm 1 dòng duy nhất là kết quả.
Giới hạn
Có ~40\%~ số test với ~n \le 9~;
~60\%~ số test với ~n \le 18~.
Sample Input
3 6 5
3 1
1 2
1 2
Sample Output
11
Comments
Thật sự đề bài này viết quá vớ vẩn. Sau khi đọc code AC thì mình xin phát biểu lại đề như sau:
Để "xây lại" ta được phép làm các thao tác:
Tìm chi phí nhỏ nhất.
thế còn cái giới hạn thì sao a ?
Giới hạn như trong đề bài
Ai đó giải thích đề cho e dc k ạ :((