The *Aurora* is an aircraft-carrying aviation submersible.

*The*Aurora.

soldiers in para-mails (you can think of these as aircraft) are being deployed to one of stations on the main continent. To travel to their respective stations, soldiers may either fly there directly with their para-mail or hitch a ride on the *Aurora*, which will make one journey from station to station to station … all the way to station . Coincidentally, this is the only route to travel between stations; that is, if a soldier wanted to travel via their own para-mail instead, they would also have to take the same route as the *Aurora* (because flying too far from the main route is unsafe). For each station from to , it takes exactly seconds to travel to station via para-mail or seconds via the *Aurora* . Whenever one or more soldiers reach their station and are flying via the *Aurora*, the *Aurora* must make a stop to let all soldiers who are deployed at that station get off. The total time the *Aurora* stops is , where is the number of soldiers that get off at that station. The soldiers get off one by one, so if three soldiers get off, the first soldier waits for seconds, the second soldier waits for seconds, and the last soldier waits for seconds. All soldiers and the *Aurora* will start at station .

The battle is beginning soon, and it is vital that each soldier arrives at their station as fast as possible. What is the minimum total time for all the soldiers to arrive at their stations?

#### Input Specification

The first line of input will contain and , separated by a single space.

The second line of input will contain , , and , separated from each other by single spaces.

The third line of input will contain integers, the assigned stations of each of the soldiers. They will be integers from to . At least one soldier will be deployed to station .

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [70%]

For all cases, .

#### Output Specification

The first and only line of output should contain the minimum total time for all the soldiers to arrive at their stations.

#### Sample Input 1

```
5 6
1 2 1
4 5 3 6 2
```

#### Sample Output 1

`21`

#### Explanation of Output for Sample Input 1

Soldier 3 and 5 should fly directly to their stations. The rest of the soldiers should use the *Aurora*. The total time is .

#### Sample Input 2

```
10 4
1 100000 1
4 3 4 2 3 2 4 3 1 4
```

#### Sample Output 2

`56`

## Comments

If only one soldier gets off at say, station 1, will that cause another soldier going to station 2 to have to wait another C seconds (assuming they both take the Aurora)?

EDIT: I'm stupid. The Aurora will stop for x*c seconds for x soldiersCan someone please explain sample input 2 for me, I dont see how 56 is obtained

Para-mail is too expensive, so all of the soldiers have to hitch a ride on the Aurora.

The total time (from left to right) is:

Note that Soldier #9 is already at the destination, so it takes seconds to get there.

Lets say a soldier 1 gets off before soldier 2. Will soldier 1's get-off Aurora time affect soldier 2's time?

Assuming they both take the

Aurora, yes.If soldiers 3 and 5 go to their stations, (2

2 = 4 minutes for soldier 3, and 12 = 2 minutes for soldier 5), where does the other numbers come from?The other soldiers board the

Aurora. Their time is calculated as described in the problem statement.Why let the two soldiers go by themselves? Isn't it better just to take all the soldiers on the aurora? To get from 1 to 6, it is 5 minutes, and then each soldiers leaves, so 5 minutes. This would be 10 minutes no?

The waiting time of soldiers increases if other soldiers get off before them.

If soldiers 1-4 took the aurora, then why does soldier 3 take more time than soldier 1 if she is getting off at station 3 compared to 4?

Sorry, soldiers 3 and 5 (in input order) should be the ones flying.

Oh, that makes sense. I just spent a long time trying to figure that out. I guess that's what I get for not refreshing the page...

Is there some restriction on when/how the soldiers can fly themselves in? Reading the problem, I thought that the soldiers could all para-mail in in tandem (and independent of the Aurora), but that definitely doesn't make sense in the context of the sample input.

Your thought is correct (as far as I understand it). Which part of the sample input is unclear? I'll try to explain it.

EDIT: The explanation has been updated. I change the sample a bit, but forgot to change the explanation. Sorry!I'm still in the dark a little, sorry...

If all the soldiers can just para-mail in without regard to each other or the Aurora, could they not all reach their stations within 10 units (in sample input 1)? Since B = 2, M = 6.

I'm probably just misreading badly. :)

If all soldiers use their para-mails, the total time will be

seconds.

Note that you are asked to minimize the

sumof the times instead of the maximum time.