CTNEWS - Lâu đài cát
Giới hạn- Thời gian: 0.2s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
CTN 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 (xem hình vẽ).
Tạm gọi các vùng cao hơn này là Merlons.Lâu đài có N (1<=n<=25000) Merlons,
để thuận tiện ta đánh số chúng từ 1->N;
Merlon thứ I có chiều cao M_i (1<=M_i<=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…B_N (1<=B_i<=100000) , và anh muốn thay đổi chiều
cao của các Merlon từ (A1…An) thành (B1..Bn) 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ố Ai, Bi cách nhau ít nhất 1 dấu cách
Output
Gồm 1 dòng duy nhất là kết quả.
Example
Input:
3 6 5
3 1
1 2
1 2
Output:
11
Có 40 % số test với n<=9; 60 % số test với n<=18.
- Người up: company_1
- Nguồn bài: Sưu tầm