题目描述

有 $n$ 个岛屿和 $m$ 艘船。第 $i$ 艘船航线的两个端点为岛屿 $U_i$ 和 $V_i$。

保证这些船的航线连通所有岛屿，并且没有两艘船的航线端点完全相同。每艘船只能停泊在其航线的两个端点岛屿，并且只能在这两个端点岛屿之间移动。

你需要派遣若干个船只管理员。管理员可以跟随船在岛屿之间移动。

你需要依次进行如下步骤：

1. 添加不超过 $k$ 艘船，并指定每艘船航线的两个端点；
2. 撤走任意数量的船；
3. 在每艘船上派遣任意数量的船只管理员；
4. 指定剩余每条船初始停泊在哪个岛屿。

筹备完成后，必须保证对于任意一对岛屿 $1\le u,v\le n$，都可以通过重复以下操作将货物从 $u$ 运送到 $v$：

• 货物和管理员均可以在岛屿与停靠在该岛屿的船只之间上下；
• 船只可以在其连接的两个岛屿之间往返，无论船上是否有管理员或货物。

在运输过程中的任何时刻，如果某艘船停泊在岛屿 $i$，则船上的管理员人数必须不少于 $S_i$。

对于每个满足 $0\le k\le q$ 的 $k$，求出最少需要派遣的管理员总数。

输入格式

从文件 ferry.in 中读入数据。

第一行三个整数 $n,m,q$。

第二行 $n$ 个整数，第 $i$ 个表示 $S_i$。

接下来 $m$ 行，第 $i$ 行两个整数 $U_i,V_i$，表示第 $i$ 艘船的航线端点。

输出格式

输出到文件 ferry.out。

对于每个 $k=0,1,\ldots,q$，输出一行一个整数，表示最多添加 $k$ 艘船时最少需要派遣的管理员总数。

样例 1

输入

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

输出

7

样例 2

输入

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

输出

7
5

样例 3

输入

3 3 0
1 1 1
1 2
1 3
2 3

输出

2

样例 4

输入

8 7 0
2 2 2 2 2 2 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

输出

14

样例 5

输入

8 7 0
16 39 36 23 15 48 23 56
1 2
1 3
2 4
2 5
3 6
3 7
7 8

输出

245

样例 6

输入

10 13 4
314 159 265 358 979 323 846 264 338 327
1 2
1 4
2 3
2 5
3 6
4 5
4 7
5 6
5 8
6 9
7 8
8 9
9 10

输出

3139
2901
2722
2567
2461

数据范围与约定

对于所有测试数据，满足：

$$1\le n\le 2\times 10^5, \qquad n-1\le m\le 4\times 10^5, \qquad 0\le q\le 2\times 10^5, \qquad 1\le S_i\le 10^9.$$

本题开启合理的子任务依赖。

子任务编号	特殊性质	分值
1	$m=n-1$，$S_i\le 2$，$U_i=i,V_i=i+1$，$q=0$	12
2	$m=n-1$，$U_i=i,V_i=i+1$，$q=0$	13
3	$m=n-1$，$q=0$	12
4	$q=0$	13
5	$n\le 16$	8
6	$n\le 3000$	18
7	无	24