問題文

$N$ 頂点 $M$ 辺からなる単純有向グラフが与えられます。各頂点には $1$ から $N$ までの番号がつけられており、 $i$ 番目の辺は $A_i$ から $B_i$ に伸びる辺です。

いま、ここにいくつかの有向辺を加えて次の条件を満たすようにする時、加える辺の最小値はいくつですか。

条件：加えてできるグラフも単純有向グラフである。また、すべての頂点について、その頂点から出ている辺が存在するのであればその頂点に入ってくる辺は $K$ 本以上である。

入力

$N$$\ $$M$$\ $$K$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$

• $2\leqq $ $ N $ $ \leqq2×10^5$
• $1\leqq $ $ M $ $ \leqq$ $\mathrm{min}$$(2×10^5,N(N-1))$
• $1\leqq $ $ K $ $\leqq N-1$
• $1\leqq $ $A_i$ $\leqq N$
• $1\leqq $ $B_i$ $\leqq N$
• $A_i \ne B_i$
• 同じ$(A_i,B_i)$の組は存在しない。つまり、全ての$1\leqq $ $ i $ $ < $ $ j $ $ \leqq $ $ M$をみたす$(i,j)$の組について、$A_i $ $ \ne $ $ B_i$あるいは$A_j $ $ \ne $ $ B_j$が成り立つ。
• 入力は全て整数

出力

答えを出力してください。

サンプル

3 1 1
1 2

1

3 2 2
1 2
2 3

4

9 6 5
2 5
5 8
7 6
1 2
1 3
5 7

25