配点 : 100 点
問題文
在这个世界上 有 N 个国家存在,这些国家有 1, 2, 3, \ldots, N 。 N 个国家到目前为止完全没有互相合作过,但由于各国之间的差距越来越大,寻求援助的国家也在增加,因此决定建立外交关系并互相提供援助。
各国的当前状况用两个整数表示。 X_i, P_i 什么时候可以工作X_i 是国家 i 的最大援助授受量,P_i 是根据援助量可以获救的国民人数。
具体来说,
X_i \ge 0 国是可以向其他国家提供援助的国家,一年内最多可以提供总计 |X_i| 的援助。
X_i < 0 国是可以接受其他国家援助的国家,一年内最多可以接受总计 |X_i| 的援助。
另外,如果国家 i 从其他国家总共接受了 x \ (x \le |X_i|) 的援助,P_i \times x 名国民可以得到救助。
目前,各国之间都没有建立外交关系,并且计划在接下来的 Q 年内建立外交关系。 该计划是每年建立一个外交关系,j 第 n 年的年初,国 a_j 和国家 连接 b_j 将建立外交关系。
这个 Q 按照年度计划顺序建立外交关系时,j 第 n 年能够通过支援救助的最大人数为每个 j ,请求解。 在
但某国可以提供支援的国家是,直接建立外交关系的国家,或通过多个外交关系间接连接的国家。
制約
- 所有输入均为整数
- 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 < 0)
- P_i = 0 \ (X_i \ge 0)
- 1 \le a_i, b_i \le N
- a_i \ne b_i
- i \ne j 什么时候 (a_i, b_i) \ne (a_j, b_j)
入力
输入是按以下格式从标准输入给出的。
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 输出第 n 年能够被救助的最大人数。
入力例 1
3 2 0 3 0 -4 2 2 1 3 1 2
出力例 1
4 8
- 第一年的话,从国家 1 向国家 3 提供一定量的支援, 2 可以救助4 人。
- 在第 2 年,从国家 1 向国家 3 提供数量 1 的支援,以及从国家 2 通过国家 1 向国家 3 提供数量 3 的支援后,总计 8 人。
入力例 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
4 -2 1 -3 5 -1 2 -3 8 3 1 2 2 3 3 4
出力例 3
0 0 0
- 没有能够提供支援的国家存在,因此无论建立多少外交关系,可以拯救的人数也只是 0 人。