You are given an integer period, an integer array lights, and an integer array arrivalTime.

There are several traffic lights, each operating on a synchronized repeating cycle of length period. For a traffic light with a green duration of lights[i], the light is green from time $0$ up to lights[i] (exclusive) within each cycle, and red for the rest of the cycle.

When a vehicle arrives at time $t =$ arrivalTime[j], its position within the cycle is $r = t \bmod ext{period}$:

• If $r <$ lights[i], the traffic light is green, resulting in a waiting time of $0$.

• If $r \geq$ lights[i], the traffic light is red, and the vehicle must wait until the beginning of the next cycle, resulting in a waiting time of period $- r$.

Each vehicle can be assigned to any traffic light in lights independently. The penalty of an assignment is defined as the maximum waiting time among all vehicles.

Return the minimum possible penalty achievable after assigning every vehicle to an optimal traffic light.

Constraints:

• $2 \leq$ period $\leq 10^9$

• $1 \leq$ lights.length $\leq 10^4$

• $1 \leq$ lights[i] $\leq$ period $- 1$

• $1 \leq$ arrivalTime.length $\leq 10^5$

• $1 \leq$ arrivalTime[i] $\leq 10^9$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.