AT_ttpc2019_h 救援

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_h この世界には $ N $ 個の国が存在し、これらの国には $ 1,\ 2,\ 3,\ \ldots,\ N $ の番号が付いています。 $ N $ 個の国々はいままで全く協力をし合ってきませんでしたが、国ごとの格差が大きくなり、支援を求める国々が増えてきたので国交を結びお互いに支援をし合うことにしました。 各国の現在の状況は、2 つの整数 $ X_i,\ P_i $ で表され、$ X_i $ は国 $ i $ の支援の最大授受量、$ P_i $ は支援の量に応じて助けられる国民の人数を表しています。 正確には、 $ X_i\ \ge\ 0 $ の国は他国への支援を行える国で、1 年間で合計 $ |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 $ 年目に助けられる人数の最大値を出力せよ。

### 制約 - 入力は全て整数 - $ 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\