The Toronto Transit Commission is staking their image on being The Faster Way to get around Toronto, with a reputation for speedily getting commuters to their destination.
A particular bus route consisting of stops starts at station and ends at station . At present, there are passengers waiting for a bus in station , with the -th commuter wishing to get off at stop . Conveniently, it turns out that each passenger wants to get off at a different station.
As station manager at station , your job is to get them to their destinations as quickly as possible.
Two buses have arrived, a regular bus and a Rocket bus. The regular bus will stop at any station on the route as long as a passenger wishes to get off. The Rocket bus will only stop at of the stops, and only if someone wishes to disembark. Whenever a bus stops, it spends minute letting people get off. These are also really fast buses we are talking about, such that it takes no time for a bus to move from one station to the next.
You would like to minimize the total amount of time passengers spend riding The Faster Way (lest it be branded The Slower Way) by optimally assigning passengers at station to either the regular bus or the Rocket. How much time will the passengers have spent cumulatively before they reach their destinations, if you do your job properly?
Scoring
For all cases, and .
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
Input Specification
The first line of input will contain the integers , and .
The next line of input will contain integers in the range , representing which of the stops the Rocket stops at. The stops will be pairwise distinct.
The last line of input will contain integers, with the -th representing . These values will be pairwise distinct.
Output Specification
The minimum cumulative time taken by commuters to get to their destinations.
Sample Input
3 2 2
1 2
1 2
Sample Output
2
Explanation
Assign the first passenger to the regular bus, and the second to the Rocket bus. The total amount of time they will spend together is minutes, and they will both be off at their stations after minute.
Comments
In the input, the stops on the route go up to N, even though the question specifications said it would only be up to N - 1.