Table of Contents

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 first d
hours at a flat 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 first 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

Solution Code

#include<stdio.h>
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    int L[n1], R[n2];
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {

        int m = l+(r-l)/2;


        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);

        merge(arr, l, m, r);
    }
}

void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

int main(){
    int n,d,r,i,sum,temp;

    while(scanf("%d%d%d",&n,&d,&r)&& n && d && r)
    {
     int m[n],e[n];
     for(i=0;i<n;i++){scanf("%d",&m[i]);}
     for(i=0;i<n;i++){scanf("%d",&e[i]);}
     mergeSort(m, 0, n-1);
     mergeSort(e, 0, n-1);
    sum = 0;
    for (i = 0; i < n; ++i)
        {
            temp = m[i] + e[n-i-1]-d;
            if (temp > 0)
                sum+=temp;
        }
        printf ("%d\n", sum * r);





    }
    return 0;

}
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn
Share on pinterest
Pinterest
Share on whatsapp
WhatsApp
Share on email
Email
Md. Nurnobi Hosen
Md. Nurnobi Hosen

Student of Computer Science and Engineering at Daffodil International University,Main Campus ,Dhanmondi.
Web and App Developer also expart of wordpress customization

All Blog Posts »
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x