Bad Multitasking

Interview

Time limit2sMemory limit1024 MB

Summary

Each second the first queued task runs up to b operations, then goes to the back if unfinished. Find the second when the first task (a1) finishes.

Level: Medium5 of 10
Topics: Simulation, Greedy, Math
Solved: No attempts yet

Problem

Saving the world is not easy, and trouble comes at every step. Once again Eggsy slipped into Poppy Adams's office and got into trouble. Poppy appeared on the screen and said the agent is too predictable, and she is always a few steps ahead. The program that destroys the antidote to the virus she spread has already started, and nothing can stop it. The world will be destroyed.

Eggsy is the agent of the best secret service, so he quickly took out his laptop, found the IP address of the server running the destruction program, and hacked it. It turned out to be Poppy's personal computer, and she is not very good with computers. Her operating system, MS ADOS, does not support parallel execution, so all programs run in a single thread. The system keeps a queue of tasks. Once per second, the first task in the queue starts running. In one second, a program can perform at most $b$ operations. If a program finishes all its required operations, it is removed from the queue. Otherwise, it moves to the end of the queue to continue later.

Eggsy was discovered quickly, and the server password was changed, so he lost access. Before that, he learned that the destruction program needs $a_1$ operations to finish. He also learned that $n-1$ other tasks with $a_2, a_3, \ldots, a_n$ operations were added to the queue. He now wants to know how much time he has to reach Poppy before the destruction program finishes. Find the number of seconds the destruction program needs to finish.

Input

The first line contains two integers $n$ and $b$ , the total number of programs running on the server and the maximum number of operations the server can perform in one second ( $1 \le n \le 10^5$ , $1 \le b \le 10^9$ ).

The next line contains $n$ integers $a_i$ , the number of operations for the destruction program and the programs Eggsy added, in the order they are in the queue ( $1 \le a_i \le 10^9$ ).

Output

Print one line containing the number of seconds after which the destruction program finishes.

Hint

In the second sample, the second-by-second sequence goes as follows:

Second 1: the first program (the destruction program) runs, performs 2 operations, then moves to the end of the queue.
Second 2: the second program runs, performs 2 operations, finishes, and is removed from the queue.
Second 3: the third program runs, performs 2 operations, then moves to the end of the queue.
Second 4: the fourth program runs, performs 1 operation, finishes, and is removed from the queue.
Second 5: the first program (the destruction program) runs, performs 2 operations, then moves to the end of the queue.
Second 6: the third program runs, performs 2 operations, then moves to the end of the queue.
Second 7: the first program (the destruction program) runs, performs 2 operations, finishes, and is removed from the queue.

What the programs do after that does not matter. As shown, the destruction program finishes after 7 seconds.

Examples2

Example 1
Input
```
5 1
3 4 3 1 2
```
Expected output
```
10
```
Example 2
Input
```
4 2
6 2 5 1
```
Expected output
```
7
```