You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这天牛宝宝正在做饭，一共有N种食材可供牛宝宝使用。
但是某两种食材如果放在一起就会让食物变得很难吃。当一道菜里难吃的食材组合大于K时，这道菜就会变成黑暗料理。
每种食材有一个健康值Ai，一份料理的健康值是将所用食材的健康值加起来。
请问牛宝宝在不做黑暗料理的情况下，能做出的最健康的菜是多少？

输入格式

第一行三个整数，分别是食材种类N、难吃组合的数目M、临界值K。
第二行一共N个整数，第i个数表示第i种食材的健康值Ai。
接下来M行，每行两个整数Bi、Ci，表示第Bi种菜和第Ci种菜是一个难吃组合。

输出格式

一个整数，表示非黑暗料理的最大健康值，保证答案有解。

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

12

说明/提示

对于30%的数据，满足M=0；
对于额外40%的数据，满足0<N≤16；
对于100%的数据，满足0<N≤20，0≤M≤N^2，
$0≤Ai≤10000，1≤Bi，Ci≤N，且Bi\not=Ci。$