Lâu đài cát (VOJ)

Link:http://vn.spoj.pl/problems/CTNEWS/

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.

Solution:

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int N,X,Y;
int a[25001],b[25001];
long long int res=0;

int main()
{
 
 freopen("TEST.INP","r",stdin);
 freopen("TEST.OUT","w",stdout);
 
 cin >> N >> X >> Y; 
 
 for(int i=0;i<N;i++)
  scanf("%d %d",&a[i],&b[i]);
 /*
 for(int i=0;i<N;i++)
  cout << a[i] << ",";
 */ 
 sort(a,a+N);
 sort(b,b+N);
 /*
 for(int i=0;i<N;i++)
  cout << a[i] << ",";
 */
 for(int i=0;i<N;i++)
  if(a[i]<b[i])
   res+=(b[i]-a[i])*X;
  else
   res+=(a[i]-b[i])*Y;
 cout << res;

 return 0; 
}