暂无测试数据。

题目描述

小扣发现一个长度为 $n$ 的神秘数列$a$，他想要分析这个数列的神秘程度。 分析过程：首先，用数列$a$ 生成一个 $1 \sim n$ 的排列$b$，满足所有的 $b_i$ 是 $a_i$ 的倍数。 $1 \sim 3$的所有排列：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

其次，将数列$b$ 划分为两种：

第一种：数列$b$ 的逆序对数量为偶数。 第二种：数列$b$ 的逆序对数量为奇数。

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。例如1.3.2.1的逆序对数为3。其中第三个数 2前比它大的数有1个，第四个数1前比它大的数有2个，因此总的逆序对数为1+2=3。 因为合法的数列b可能存在多种，第一种合法的b序列的数量为cnt1，第二种合法的b序列的数量为cnt2。那么数列 a 的神秘程度为:ans = cnt1-cnt2。 请你帮蒜头君计算出数列a的神秘程度。

输入格式

第一行包含三个正整数 $n, m, k$，分别表示地图上点的个数、双向直达的点对数量、每段行程最多的转车次数。

第二行包含 $n - 1$ 个正整数，分别表示编号为 $2, 3, \ldots, n$ 的景点的分数。

接下来 $m$ 行，每行包含两个正整数 $x, y$，表示点 $x$ 和 $y$ 之间有道路直接相连，保证 $1 \le x, y \le n$，且没有重边，自环。

输出格式

输出一个正整数，表示小熊经过的 $4$ 个不同景点的分数之和的最大值。

样例 #1

样例输入 #1

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

样例输出 #1

27

样例 #2

样例输入 #2

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

样例输出 #2

7

提示

【样例解释 #1】

当计划的行程为 $1 \to 2 \to 3 \to 5 \to 7 \to 1$ 时，$4$ 个景点的分数之和为 $9 + 7 + 8 + 3 = 27$，可以证明其为最大值。

行程 $1 \to 3 \to 5 \to 7 \to 8 \to 1$ 的景点分数之和为 $24$、行程 $1 \to 3 \to 2 \to 8 \to 7 \to 1$ 的景点分数之和为 $25$。它们都符合要求，但分数之和不是最大的。

行程 $1 \to 2 \to 3 \to 5 \to 8 \to 1$ 的景点分数之和为 $30$，但其中 $5 \to 8$ 至少需要转车 $2$ 次，因此不符合最多转车 $k = 1$ 次的要求。

行程 $1 \to 2 \to 3 \to 2 \to 3 \to 1$ 的景点分数之和为 $32$，但游玩的并非 $4$ 个不同的景点，因此也不符合要求。

【数据范围】

对于所有数据，保证 $5 \le n \le 2500$，$1 \le m \le 10000$，$0 \le k \le 100$，所有景点的分数 $1 \le s_i \le {10}^{18}$。保证至少存在一组符合要求的行程。

测试点编号	$n \le$	$m \le$	$k \le$
$1 \sim 3$	$10$	$20$	$0$
$4 \sim 5$	$10$	$20$	$5$
$6 \sim 8$	$20$	$50$	$100$
$9 \sim 11$	$300$	$1000$	$0$
$12 \sim 14$	$300$	$1000$	$100$
$15 \sim 17$	$2500$	$10000$	$0$
$18 \sim 20$	$2500$	$10000$	$100$