问题 2000. -- 宝藏

2000: 宝藏

时间限制: 1 Sec  内存限制: 128 MB
提交: 10  解决: 2
[提交][状态][讨论版]

题目描述

天顶星人与魔法世界的战争可以追溯到远古时代,这就是传说中的“神话时代”又称“众神陨落时代”。这场星际战争毁灭了人类创造的大部分科技文明,当时幸存的人类为了保存文明的火种,在地下建造了一个神秘的宝藏,该宝藏是没有出口,只有入口,现在修罗王在与天顶星人的接触中查到了宝藏的线索,知道宝藏总共有N个分岔口,在分岔口处是有科技源的,每个科技源都有一个价值。他偷偷带领了M个人来挖宝藏,为了安全起见,在每个分岔口必须至少留一个人下来,这个留下来的人可以挖科技源(每个人只能挖一个地方的科技源),这样才能保证不会迷路,而且这个迷宫有个特点,任意两点间有且只有一条路可通。请问如何才能多挖些科技源回去。

输入

第1行:两个正整数N,M 。N表示宝藏点的个数,M表示挖宝藏人数。(n≤1000,m≤100)
第2行:N个整数,第i个整数表示第i个宝藏的价值。(保证|wi|<maxint)
第N+2行:两个非负整数A和B,表示A通向B,当A=0,表示A是入口。(保证A,B≤n)

输出

输出最多挖回的价值。

样例输入

4 3
5 6 2 4
1 2
0 1
2 3
3 4

样例输出

13

提示

来源

[提交][状态]