The working day ended, and the business center employees gathered at home. The business center is an N-storey building, the floors are numbered from 1 to N from bottom to top. All employees want to go down to the parking lot, which is located in the basement one floor below the first one. The business center is equipped with an elevator that can carry no more than K people at a time. The elevator moves up or down one floor in one second, boarding and disembarking passengers occur instantly. Initially, the elevator is located at the parking level. It is known how many people want to go down to the parking lot from each
from N floors. Determine the minimum time required to transport all employees of the business center to the parking lot.
The first line of the input contains the largest possible number of people in the elevator K, 1 ≤ K≤ 109
The second line contains the number of floors in the business center N, 1 ≤ N≤ 105
The next N lines contain non-negative integers – number of people waiting for an elevator at 1, 2, … , Nth floor, respectively, these numbers do not exceed 109 each. There is at least one person in the building.
The program should output exactly one integer – the shortest time in seconds in which all people can be transported to the parking lot.
|
Enter |
Output |
Note |
2
3
3
0
1 |
8 |
The elevator transports 2 people, the building has 3 floors. The elevator goes up to the first floor in 1 s, picks up 2 people and goes down to the parking lot in 1 s, then the elevator goes up to the first floor, picks up 1 person, goes up to the third floor with it, picks up 1 person and goes down to the parking lot. The ascent to the third floor takes 3 seconds, the descent – 3 more s. |