徐老师的全国巡演

题目描述

五一节到了，徐老师受邀乘坐高铁到全国n个城市给选手们培训，由于时间有限，徐老师只能从n个发出邀请的城市当中选择四个参加人数之和最多的城市（不能选择徐老师出发的城市，该城市编号为1），并且还要考虑城市与城市之间的转车次数，为了提高效率，徐老师从一个选择城市到另一个选择城市的转车次数不能超过k次。如果城市之间的每条高铁线路都是双向的，已知m条连接两个城市的铁路和每个城市的培训报名人数，你能帮助徐老师安排行程吗?

徐老师要从编号为1的城市出发，最后返回编号为1的城市，转车经过的城市没有任何限制，例如所选四个城市的编号分别是A,B,C,D，从A到B也可以经过1、C、D等任意城市。

输入格式

第一行包含 3 个正整数 n,m, k，分别表示发出邀请城市的个数、高铁轨道的数量、每段行程最多的转车次数。

第二行包含 n−1 个正整数，分别表示编号为 2,3,...,n的城市报名人数。

接下来 m 行，每行包含两个正整数 x, y，表示编号 x的城市 和 编号y的城市之间有铁路直接相连，保证 1≤x,y≤n，且没有重边，自环。

输出格式

第一行输出一个正整数，表示徐老师选择的四个城市人数之和的最大值。

样例

样例输入

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

样例输出

27

提示

【输入输出样例说明】

当计划的行程为 1 → 2 → 3 → 5 → 7 → 1 时，4 个城市的人数之和为 9+7+8+3 = 27，可以证明其为最大值。

【数据规模与约定】

对于所有数据，保证 5≤n≤2500, 1≤m≤10000, 0≤k≤100, 城市的报名人数1≤si≤10^18。