# [UVA11389]The Bus Driver Problem

Posted by John on 2016-01-13
Words 406 and Reading Time 2 Minutes
Viewed Times

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

>