問題文

ペンギン学園の学長である penguinman は、生徒達のためにパンを幾つか仕入れ、購買部で売ることにしました。

仕入れられるパンは $N$ 種類あり、penguinman はその中からちょうど $K$ 個を仕入れて売ります。同じ種類のパンを幾つ仕入れても構いませんし、$1$ つも仕入れないパンがあっても良いです。

仕入れにあたって生徒達にアンケートを取ったところ、$M$ 個の回答が得られ、$i\ (1\leq i\leq M)$ 個目の回答は以下のものでした。

• $x_i$ 種類目のパンをちょうど $y_i$ 個仕入れて欲しい。

penguinman は生徒達の要望に出来る限り答えたいです。$B_i$ を $i$ 種類目のパンの仕入れ数とした時、適切にパンを仕入れることで $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$ を最小化してください。

$B_i$ はパンの仕入れ数であるため非負整数である必要があり、また先述の条件より $B_i$ の総和は $K$ になる必要があります。この問題の制約下では解は $10^{18}$ 以下に収まります。

$T$ 個のテストケースに答えてください。

入力

入力の $1$ 行目は以下の通りです。

\(T\)

続いて $T$ 個のテストケースが以下のフォーマットで順番に与えられます。

\(N\) \(M\) \(K\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(\vdots\)
\(x_M\) \(y_M\)

• $1\leq T\leq 100$
• $1\leq N,\ M\leq 2\times 10^5$
• $1\leq K\leq 10^9$
• $1\leq x_i\leq N$
• $1\leq y_i\leq 10^9$
• $M\times \max(K,\ \max(y))^2\leq 10^{18}$
• $T$ 個のテストケース全体における $N,\ M$ の総和はそれぞれ $2\times 10^5$ を超えない
• 入力は全て整数

出力

$T$ 行に渡って出力してください。$k$ 行目には $k$ 個目のテストケースにおける $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$ の最小値を出力してください。

サンプル

2
2 2 3
1 1
2 2
3 4 10
1 4
2 3
1 4
2 4

0
1

3
5 8 93
2 11
3 80
3 58
1 78
4 8
4 71
1 39
2 30
6 10 56
5 31
1 48
6 8
2 24
4 75
2 83
5 80
5 31
4 60
2 63
6 10 480
5 74
3 64
5 40
3 52
2 98
2 83
2 5
6 53
6 41
2 88

7659
17317
6216