The Legendary Huron airlines is going through a tough time: tariffs are increasing and their customer satisfaction is plummeting. A particular customer complaint that they receive often is that the time that it takes to board one of their planes is too long. To try and tackle this problem their optimization department is developing an algorithm and your job is to test it.

For a set of $$$N$$$ passengers the algorithm outputs a fixed order $$$A$$$ in which the passengers are supposed to board the plane. Given this order your job is to compute how much time will it take to onboard the $$$N$$$ passengers. For the $$$i$$$-th passenger you know in what row ($$$r_i$$$) their seat is and how many seconds ($$$k_i$$$) it takes them to store their luggage in the overhead compartment. It takes $$$1$$$ second to move from the $$$\rho$$$-th row to the $$$(\rho+1)$$$-th one, thus the total time it takes the $$$i$$$-th passenger to take a seat is $$$r_i + k_i$$$ (since the door can be seen as row $$$0$$$ of the plane). It's impossible for two or more passengers to be on the same row at the same exact time. Hence, no two passengers can onboard at the same time.

A new rule was added since no one wants to wait on the aisle. This rule states that a passenger is only allowed to start onboarding if all of the previous passengers that are seating in a closer row (to the door) than them have already seated. More formally, this rule states that the $$$i$$$-th passenger can only begin to onboard the plane at time $$$\tau$$$ if there's no $$$j \lt i$$$ such that $$$r_j \leq r_i$$$ and $$$t_j + r_j + k_j \gt \tau$$$, where $$$t_j$$$ is the time at which the $$$j$$$-th passenger started onboarding the plane.

Help the Legendary Huron airlines improve their customer satisfaction!