Robot on a Conveyor Belt

Interview

Time limit1sMemory limit512 MB

Summary

Simulate a rotating conveyor belt where robots load, advance when possible, and stop once K cells have zero durability, reporting the step count.

Level: Medium6 of 10
Topics: Simulation, Implementation, Queue, Array
Solved: No attempts yet

Problem

There is a conveyor belt of length N, and a belt of length 2N wraps around this conveyor belt and rotates over and under it. The belt is divided into 2N cells with a spacing of 1, and each cell is numbered from 1 to 2N as shown in the figure below.

When the belt rotates by one cell, cells 1 through 2N-1 move to the positions of the next-numbered cells, and cell 2N moves to the position of cell 1. The durability of cell i is $A_i$ . In the figure above, the position of cell 1 is called the "loading position", and the position of cell N is called the "unloading position".

We want to place box-shaped robots onto the conveyor belt one at a time. A robot can only be placed at the loading position. Whenever a robot reaches the unloading position, it is immediately removed. A robot can move on its own on the conveyor belt. When a robot is placed at the loading position or a robot moves to some cell, the durability of that cell immediately decreases by 1.

We want to move robots to the other side using the conveyor belt. During the process of moving robots, the following events occur in order.

The belt rotates by one cell together with the robots on each cell.
Starting from the robot that was placed on the belt first, if a robot can move one cell in the direction the belt rotates, it moves. If it cannot move, it stays still.
1. For a robot to move, the cell it wants to move to must not contain a robot, and the durability of that cell must be at least 1.
If the durability of the cell at the loading position is not 0, place a robot at the loading position.
If the number of cells with durability 0 is at least K, the process ends. Otherwise, return to step 1.

Find which step was in progress when the process ended. The first step performed is step 1.

Input

The first line gives N and K. The second line gives $A_1, A_2, \dots, A_{2N}$ .

Output

Output which step was in progress when the process ended.

Constraints

$2 \le N \le 100$
$1 \le K \le 2N$
$1 \le A_i \le 1,000$

Examples4

Example 1
Input
```
3 2
1 2 1 2 1 2
```
Expected output
```
2
```
Example 2
Input
```
3 6
10 10 10 10 10 10
```
Expected output
```
31
```
Example 3
Input
```
4 5
10 1 10 6 3 4 8 2
```
Expected output
```
24
```

Example 4

Input

5 8
100 99 60 80 30 20 10 89 99 100

Expected output