#2000. 「CSP-S 2022」假期计划

内存限制:512 MiB 时间限制:2000 ms 输入文件:holiday.in 输出文件:holiday.out
题目类型:传统 评测方式:文本比较
上传者: HHOJ

题目描述

小熊的地图上有 个点,其中编号为 的是它的家、编号为 的都是景点。部分点对之间有双向直达的公交线路。如果点 、……、 之间均有直达的线路,那么我们称 之间的行程可转车 次通达;特别地,如果点 之间有直达的线路,则称可转车 次通达。

很快就要放假了,小熊计划从家出发去 不同的景点游玩,完成 段行程后回家:家 景点 A 景点 B 景点 C 景点 D 家且每段行程最多转车 次。转车时经过的点没有任何限制,既可以是家、也可以是景点,还可以重复经过相同的点。例如,在景点 A 景点 B 的这段行程中,转车时经过的点可以是家、也可以是景点 C,还可以是景点 D 家这段行程转车时经过的点。

假设每个景点都有一个分数,请帮小熊规划一个行程,使得小熊访问的四个不同景点的分数之和最大。

输入格式

从文件 holiday.in 中读取数据。

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

第二行包含 个正整数,分别表示编号为 的景点的分数。

接下来 行,每行包含两个正整数 ,表示点 之间有道路直接相连,保证 ,且没有重边,自环。

输出格式

输出到文件 holiday.out 中。

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

样例

样例 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

样例 1 解释

当计划的行程为 时, 个景点的分数之和为 ,可以证明其为最大值。

行程 的景点分数之和为 、行程 的景点分数之和为 。它们都符合要求,但分数之和不是最大的。

行程 的景点分数之和为 ,但其中 至少需要转车 次,因此不符合最多转车 次的要求。

行程 的景点分数之和为 ,但游玩的并非 个不同的景点,因此也不符合要求。

样例 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

样例 3

见附件中的 holiday/holiday3.inholiday/holiday3.ans

数据范围

对于所有数据,保证 ,所有景点的分数 。保证至少存在一组符合要求的行程。

测试点编号