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\ <\ 0 $ 时，表示国家可以接受来
自其他国家的支援，一年内最多接受总量为$
|X_i| $ 。

另外，国家$ i $ 从其他国家合计$ x\ (x\
\le\ |X_i|) $ 的支援$ P_i\ \times\ x $人
我知道我能帮助一个国民。

现在所有国家还没有建立国交，计划未来 $ Q
$ 年内建立国交。
每年只能签订一项国交协议，第 $ j $ 年的
计划是国家 $ a_j $ 和国家 $ b_j $签订
国交协议。

按照这些 $ Q $ 年内的计划，依次建立国交
关系，求解每年建立国交后能够帮助的最大人
数。

但是，某个国家可以进行支援的国家是直接建
交的国家，或者是经由多个邦交间接连接的国
家。

输入以以下形式由标准输入给出。

$ 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\ <\ 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) $

- 在第二年，从国家1到国家3提供2美元的援
助，可以帮助4美元的人。-第二年，从国家1
到国家3提供1美元的数量援助，从国家2到国
家3通过国家1提供3美元的数量援助，总共可
以帮助8美元。

- 因为不存在可以支援的国家，所以无论怎
么缔结邦交都能得救的人数是$0美元。