P15796 [MX-J28-T3] "Cfz Round 8" Juice Problem

There are $n+1$ cups in front of Yuki, numbered from $0$ to $n$. For cups $1$ to $n$, both the capacity and the current amount of juice are fixed: cup $i$ has capacity $a_i$ and currently contains $b_i$ units of juice. Cup $0$ has capacity $10^9$, and the amount of juice in it is not fixed. Yuki defines operation $i$ as pouring the juice in cup $i-1$ into cup $i$. If at this time the amount of juice in cup $i$ exceeds its capacity, the juice will overflow until the amount of juice in the cup becomes equal to its capacity. Now Yuki has $q$ queries. The $i$-th query gives two parameters $v_i, p_i$. You need to find: if cup $0$ contains $v_i$ units of juice, then after Yuki performs operations $1,2,\dots,p_i$ in order, how much juice will be in cup $p_i$. Note that these operations are not actually performed, meaning the queries are independent of each other.

**This problem contains multiple test cases.** The first line contains two non-negative integers $c,t$, representing the test point ID and the number of test cases. $c=0$ means this test point is the sample. Then each test case is given as follows: - The first line contains two non-negative integers $n,q$. - The next $n$ lines: the $i$-th line contains two non-negative integers $a_i,b_i$. - The next $q$ lines: the $i$-th line contains two non-negative integers $v_i,p_i$.

For each test case: - Output $q$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

### Sample 1 Explanation This sample contains $1$ test case. For the $1$st query: - Cup $0$ contains $5$ units of juice. After pouring it into cup $1$, since cup $1$ has capacity $4$ and $5 \gt 4$, the juice overflows. Therefore, cup $1$ finally contains $4$ units of juice. For the $2$nd query: - After operation $1$, cup $1$ contains $0$ units of juice. - After operation $2$, cup $2$ contains $8$ units of juice. For the $3$rd query: - After operation $1$, cup $1$ contains $3$ units of juice. - After operation $2$, cup $2$ contains $9$ units of juice. - After operation $3$, cup $3$ contains $13$ units of juice. ### Constraints For all testdata: - $1 \le t \le 3$. - $1 \le n \le 2\times10^5$, $0 \le q \le 2\times10^5$. - For all $1 \le i \le n$, $0 \le b_i \le a_i \le 10^9$. - For all $1 \le i \le q$, $0 \le v_i \le 10^9$, $1 \le p_i \le n$. ::cute-table{tuack} | Test Point ID | $n,q \le$ | Special Property | | :-----------: | :-------: | :--------------: | | $1\sim3$ | $2\times10^3$ | None | | $4$ | $2\times10^5$ | AC | | $5\sim8$ | ^ | A | | $9$ | ^ | BC | | $10\sim13$ | ^ | B | | $14,15$ | ^ | C | | $16 \sim 20$ | ^ | None | - Special Property A: for all $1 \le i \lt n$, $a_i \ge a_{i+1}$. - Special Property B: for all $1 \le i \le n$, $a_i \le a_{i+1}$. - Special Property C: for all $1 \le i \le n$, $b_i=0$. Translated by ChatGPT 5