There are $n$ boxes located on the right bank of a river and $k$ workers, indexed from $0$ to $k - 1$, initially waiting on the left bank. A single narrow bridge connects the two banks, allowing only one worker to cross at any given moment.

Worker i requires specific durations given by time[i] = [left_i, pick_i, right_i, put_i]:

• left_i: time to cross the bridge from the left bank to the right bank.

• pick_i: time to pick up a box from the right bank.

• right_i: time to cross the bridge from the right bank to the left bank.

• put_i: time to put down a box on the left bank.

A worker i is considered less efficient than worker j if:

• left_i + right_i > left_j + right_j, or

• left_i + right_i == left_j + right_j and i > j.

The bridge usage follows these priority rules:

• If workers are waiting on both sides of the bridge, workers crossing from the right bank to the left bank always have higher priority.

• If multiple workers on the same bank are ready to cross, the least efficient worker among them crosses first.

• If all $n$ boxes have already been claimed or brought over, no worker will cross from the left bank to the right bank.

When worker i crosses to the right bank, they immediately spend pick_i time picking up a box, and then wait to cross back to the left bank. After crossing back to the left bank, they immediately spend put_i time placing the box down, after which they are available on the left bank again.

Return the timestamp at which the final worker carrying the last box finishes crossing the bridge to the left bank.

Constraints:

• $1 \leq$ n, k $\leq 10^4$

• time.length $==$ k

• time[i].length $== 4$

• $1 \leq$ left_i, pick_i, right_i, put_i $\leq 1000$

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.