[UVA11389]The Bus Driver Problem

In a city there are n bus drivers. Also there are n morning bus routes and n afternoon bus routes with various lengths. Each driver is assigned one morning route and one evening route. For any driver, if his total route length for a day exceeds d, he has to be paid overtime for every hour after the ﬁrst d hours at a ﬂat r taka / hour.

Your task is to assign one morning route and one evening route to each bus driver so that the total overtime amount that the authority has to pay is minimized.

Input

The ﬁrst line of each test case has three integers n, d and r, as described above. In the second line, there are n space separated integers which are the lengths of the morning routes given in meters. Similarly the third line has n space separated integers denoting the evening route lengths. The lengths are positive integers less than or equal to 10000. The end of input is denoted by a case with three 0’s.

Output

For each test case, print the minimum possible overtime amount that the authority must pay. Constraints • 1 ≤ n ≤ 100 • 1 ≤ d ≤ 10000 • 1 ≤ r ≤ 5

Sample Input

2 20 5 10 15 10 15 2 20 5 10 10 10 10 0 0 0

Sample Output

50 0

做個排序比大小即可，排序完就是最佳解。

#‎include‬ <iostream>; 
#include <cstdlib>; 
using namespace std; 
int main() { 
  int n = 0; 
  int d = 0; 
  int r = 0; 
  while(scanf("%d %d %d", &n, &d, &r)&&(n&&d&&r)) { 
    int morn[101] = {0}; 
    int even[101] = {0}; 
    for(int i = 0 ; i < n ; ++i) scanf("%d",&morn[i]); 
    for(int i = 0 ; i < n ; ++i) scanf("%d",&even[i]); 
    /*
    printf("%d %d %d\n",n,d,r); 
    for(int i = 0 ; i < n ; ++i) printf("%d ",morn[i]); printf("\n"); for(int i = 0 ; i < n ; ++i) printf("%d ",even[i]); printf("\n");
    */ 
    sort(morn+0,morn+n); 
    sort(even+0,even+n); 
    int sum = 0; 
    for(int i = 0 ; i 0) { 
      sum += ( (morn[i] + even[(n-i)-1])-d ) * r; 
    } 
    //printf("%d %d %d\n",i,(morn[i] + even[(n-i)-1])-d,sum); 
  } 
  printf("%d\n",sum); 
  return 0; 
}