#2643. 餐馆
餐馆
题目描述
妹的胡椒粉大卖,这辣味让食客们感到刺激,许多餐馆也买这位妹的账。有家餐馆,有条道路,这家餐馆能相互到达。妹从号餐馆开始。每一个单位时间,妹可以在所在餐馆卖完尽量多的胡椒粉,或者移动到有道路直接相连的隔壁餐馆。第家餐馆最多需要瓶胡椒粉。妹有个单位的时间,问她最多能卖多 少胡椒粉。
输入格式
第一行有两个正整数。
第二行描述餐馆对胡椒粉的最大需求量,有个正整数,表示。
接下来有行描述道路的情况,每行两个正整数描述这条道路连接的两个餐馆。
输出格式
一个整数,表示她最多能卖的胡椒粉瓶数。
样例
输入样例1
3 5
9 2 5
1 2
1 3
输出样例1
14
输入样例2
4 5
1 1 1 2
1 2
2 3
3 4
输出样例2
3
输入样例3
5 10
1 3 5 2 4
5 2
3 1
2 3
4 2
输出样例3
15
提示
对于的数据,。
对于的数据,。
对于的数据
第到第个测试点都有多个子测试。
样例解释
在样例的中,辣妹到达城市后就恰好没时间卖辣椒粉了。