Let’s solve the problem for a fixed set of tasks. Let the j-th participant has C_j tasks, the times needed for which are — A_{j,1}, A_{j,2}, \ldots, A_{j,C_j}.
To minimize the total time, each participant should perform their easiest tasks. We assume that A_{j,1} \le A_{j,2} \le \ldots \le A_{j,C_j}. Then the participant must complete a certain number S_j of the first tasks: A_{j,1}, A_{j,2}, \ldots, a_{j,S_j}. For convenience, we denote prefix sums: pref_{j,e}=A_{j,1}+A_{j,2}+\ldots+A_{j,e}. Then the total time for completing the tasks by the j-th participant is pref_{j,S_j}. And the total class time is max\{pref_{1,S_1}, pref_{2,S_2}, \ldots, pref_{N,S_N}\}. In this case, S_1+S_2+\ldots+S_N=k tasks will be completed.
The answer for a given number of tasks k is the smallest number ans_k such that there exist numbers S_1, S_2, \ldots, S_n for which:
- S_1+S_2+\ldots+S_N=k,
- pref_{1,S_1} \le ans_k,
-
pref_{2,S_2} \le ans_k,
\vdots - pref_{N,S_N} \le ans_k.
Arrays of prefix sums are increasing, so you can write it like this:
- S_1+S_2+\ldots+S_N=k,
- pref_{1,1}, pref_{1,2}, \ldots, pref_{1,S_1} \le ans_k,
-
pref_{2,1}, pref_{2,2}, \ldots, pref_{2,S_2} \le ans_k,
\vdots - pref_{N,1}, pref_{N,2}, \ldots, pref_{N,S_N} \le ans_k.
That is, if we consider all the prefix sums of all participants together, then among these numbers there must be at least S_1+S_2+\ldots+S_N=k numbers not greater than ans_k. Hence, it is very easy to find ans_k: write all the prefix sums into one array all of length i (i is the total number of tasks of all participants), sort it, and then ans_k=all_k. Indeed: among all the prefix sums (i.e., the elements of array all) there are exactly k numbers not greater than ans_k=all_k. The problem is to find ans_1+ans_2+\ldots+ans_i — this equals all_1+all_2+\ldots+all_i — it is the sum of all prefix sums.
Let’s return to the original problem. We’ll store an array sum, where sum_j is the sum of the tasks of the $j$th participant, and the number total is the current answer to the task. Each query (P_i, T_i) means that the number T_i is added to the array A_{P_i}, and it is added to the end of this array, since, by the condition, the numbers T_i are increasing. Obviously, we need to add T_i to sum_{P_i}. And to the number total (the sum of all prefix sums), you need to add the new prefix sum that has appeared, that is, the new value of sum_{P_i}.