The police of Delft has received a message that a bomb has been placed in the city’s highest building. A crisis team is formed, and they decide to evacuate the building as fast as possible. Luckily it is past five, and most people have already left the building. Using the building’s security cameras, the crisis team could easily make a list of the people left in the building, and the floors where they stay. The crisis team decides to use a single elevator for evacuation, one that happens to be at the top floor of the building.
To minimize the risk of the bomb being activated by the vibrations of the elevator, the elevator will only move down, and move down only once. An evacuation plan is made, and using the building’s intercom, the people in the building are asked to use the stairs (upwards or downwards) to the floor where they will be picked up by the elevator. The elevator happens to be located next to the stairs. Some people on the lower floors may have to leave the building using only the stairs.
The elevator needs a constant time to move down a floor, and to close its doors (time needed to open the doors is ignored). People take a constant time to walk down or up a staircase as well. At the beginning, the doors of the elevator are closed.
Your task is to write a program to make the fastest evacuation plan possible, and calculate how fast everybody in the building can reach the ground floor.
The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format:
You may assume that all people involved will fit into the elevator.
For every test case in the input file, the output should contain a single number, on a single line: the time needed to get everybody in the building on the ground floor.
3 1 1 4 5 3 5 1 0 1 1 4 5 6 0 1 2 3 4 5 10 10 20 1000 0
6 8 0