题目描述

Time Limit: 1000MS

七夕将至,牛郎和织女又要见面了。

为了刁难牛郎,王母给了牛郎一个任务,并告诉牛郎如果不能顺利完成,那么今年他和织女见面的时间就得减半。

王母的任务是让牛郎去新天界收集L个单位菖蒲。

新天界由N个小岛和M条连接小岛的桥组成。每一个时刻,每个小岛上都会长出不同数量的菖蒲。王母一共给了牛郎K个收集菖蒲的仙器,你可以认为仙器是容量是无限大,一个仙器可以收集一个岛上某个时刻生长的所有菖蒲。在每次长出菖蒲前,牛郎需要把仙器放置在K个小岛上。但是由于两次长出菖蒲的时间间隔并不长,所以牛郎每次只能将其中一个岛上的仙器移动到相邻的岛(相互间直接有桥的岛视为相邻,某一时刻开始时牛郎可以出现在任何岛上),当然牛郎也可以选择不进行移动。(即该时刻仙器与上一时刻至多只有一个的位置改变)

王母一共给了牛郎T单位时间去收集菖蒲,时刻1之前,牛郎可以任意将K个仙器放置在任何K个小岛上。(即仙器的初始位置由牛郎决定)

Sample 1:

样例输入:

3 2 1 3 1000

2 3

1 2

273 296 18

341 258 621

617 736 587

样例输出:

Yes

1653

说明:[2] -> [3] -> [2]

Sample 2:

样例输入:

3 2 2 3 1000

2 3

1 2

99 99 1

1 99 99

99 1 99

样例输出:

No

496

说明: [1,2] -> [1,2] -> [1,3]

时刻2时不能将1放到3,因为不可1、3岛不直接联通,且不可将岛1上的仙器暂放到岛2上。

Sample 3:

样例输入:

8 5 5 4 10000

6 1

8 4

4 5

6 2

8 5

395 437 387 86 232 111 350 15

610 558 533 119 798 472 971 253

962 581 614 194 87 260 24 483

684 989 865 463 735 106 884 363

样例输出:

Yes

12092

注意:

同一岛无论任何时候最多只能有一个仙器。也就是说不能把一个仙器移动到已存在仙器的岛上。

30% N <= 5, T <= 10

50% N <= 10, T <= 100

100% N <= 10, T <= 1000

1<= K <= 5

1 <= N <= 10

0 <= M <= 50

1 <= T <= 1000

0 <= L <= 2^31 - 1

0 <= A(i,j) <= 1000

输入格式

Line 1 : 5个整数分别为 N, M, K, T, L

Line 2..M + 1 : 每行两个整数a, b,表示岛a, b之间有桥相连,保证每座桥只输入一次。。

Line M + 2 .. M + T + 1 : 每行N个整数,第M + 1 + i行第j个数表示第i个时刻岛j上长出的菖蒲数量。

输出格式

Line 1 : 如果牛郎能够收集到大于等于L个单位的菖蒲,输出"Yes"否则输出"No"。

Line 2 : 一个整数,牛郎能够收集到的菖蒲的极大值。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论