Making an elevator control algorithm is a very complicated task. The main purpose of the elevator control systems is to minimize the total waiting time of the people at the corridor. People don't care about the time passed in the elevator, but they don't have any patience to wait for an elevator.

Question: You should make a program for an N-floor building to let people go to work as quickly as possible. There is only one elevator with the capacity for M people. The elevator travels between two consecutive floors in 1 second and people enter or leave the elevator in 1 second. The elevator is resting on the ground floor (floor 1) at the beginning.

Input specification
There are two integers N (2 ≤ N ≤ 11) and M (M ≤ 30) on the first line of the input. The second line of the input, has N-1 integers pi (pi ≤ M) that represent the number of people in each floor starting from the second floor.

Output specification
The output has a single integer that is the minimum total waiting time.

Explanation: Elevator goes to the second floor in one second. 2 people there have totally waited 2 seconds. And in one second, they get on to the elevator. Then, elevator goes down to the first floor in one second and people get off from the elevator in one second. Total time passed is 4 seconds.

Then, elevator climbs to the fourth floor in 3 seconds. The people on the fourth floor have waited 7 seconds and it makes 21 seconds totally for all 3 people. This makes totally 23 (21+2) seconds for all the people.