The Aurora is an aircraft-carrying aviation submersible.
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?
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 .
For all subtasks:
Subtask 1 [30%]
Subtask 2 [70%]
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
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