AT_ttpc2019_h 救援

这个世界上有 $N$ 个国家，这些国家有 $1,2,3,…,N$ 的号码。 $N$ 个国家到现在为止完全不合作，所以每 个国家的差距变大了，寻求支援的国家增加 了，所以决定缔结邦交互相支援。 各国目前的情况是，两个整数$ X_i,\ P_i $, 表示为$ X_i $ 国家 $ i $ 支援最大授受量$ P_i $ 表示根 据支援的量被帮助的国民的人数。 准确地说： 当$ X_i\ \ge\ 0 $ 时，表示国家可以向其他 国家提供支援，一年内最多支援总量为 $ |X_i| $ 。 当 $ X_i\

输入以以下形式由标准输入给出。 > $ N $ $ X_1 $ $ P_1 $ $ X_2 $ $ P_2 $ $ \vdots $ $ X_N $ $ P_N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_Q $ $ b_Q $

$ Q $行输出。 $ i $ 在第三行，按照预定建 交的时候 $ i $ 输出第1年能帮助的人数的最 大值。 ## 样例 #1 ### 样例输入 #1 ``` 3 2 0 3 0 -4 2 2 1 3 1 2 ``` ### 样例输出 #1 ``` 4 8 ``` ## 样例 #2 ### 样例输入 #2 ``` 4 -5 1 -3 3 1 0 6 0 5 1 4 1 2 2 4 2 3 3 4 ``` ### 样例输出 #2 ``` 5 12 12 13 13 ``` ## 样例 #3 ### 样例输入 #3 ``` 4 -2 1 -3 5 -1 2 -3 8 3 1 2 2 3 3 4 ``` ### 样例输出 #3 ``` 0 0 0 ```

### 制约 - 输入全部为整数 - $ 2\ \le\ N\ \le\ 10^5 $ - $ 1\ \le\ Q\ \le\ \min(10^5,\ N(N- 1)/2) $ - $ 0\ \le\ |X_i|\ \le\ 10^9 $ - $ \sum\ |X_i|\ \le\ 10^9 $ - $ 1\ \le\ P_i\ \le\ 10^9\ (X_i\