問題文

この世界には 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 < 0 の国は他国からの支援を受けられる国で、1 年間で合計 |X_i| までの支援を受けることができます。
また、国 i が他国から合計 x \ (x \le |X_i|) の支援を受けると、P_i \times x 人の国民を助けられることが分かっています。

今現在どの国同士も国交は結んでおらず、これから Q 年間の国交を結ぶ予定が立っています。 その予定は 1 年に一つの国交が結ばれるものになっており、j 年目のはじめには国 a_j と国 b_j が国交を結ぶ予定です。

この Q 年間予定に従って順に国交を結んでいったとき、j 年目に支援で救える人数の最大値を各 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)

入力例 1

3
2 0
3 0
-4 2
2
1 3
1 2

出力例 1

4
8

• 1 年目には、国 1 から国 3 に量 2 の支援を行うと、4 人助けることができます。
• 2 年目には、国 1 から国 3 に量 1 の支援と、国 2 から国 3 に国 1 を経由して量 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 人です。