UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3380. [Usaco2004 Open]Cave Cows 1 洞穴里的牛之一

统计 下载数据

Description

    很少人知道其实奶牛非常喜欢到洞穴里面去探险。
    洞窟里有N(1≤N≤100)个洞室,由M(1≤M≤1000)条双向通道连接着它们.每对洞室间
至多只有一条双向通道.有K(1≤K≤14)个洞室,里面放有1捆干草.牛吃1捆干草,体重指数就会增加1.
    贪吃的贝茜要到洞窟里面探险.她希望能吃尽量多的干草,但每条通道有一个宽度阈值,如果体重指数超过相应的阈值,贝茜就会被卡祝她从洞窟1出发,体重指数为0.在洞里溜达一圈后,她要返回洞窟1.    那她最多能吃多少捆干草呢?注意,贝茜经过一个洞室,不一定非要吃掉里面的干草.

Input

    第1行输入N,M,K,之后K行每行一个整数,表示在这个洞室放有一捆干草;接下来M行每行三个整数,表示一条双向通道的起点终点和宽度阈值.

Output

 
    最多能吃掉的干草数.

Sample Input

6 7 5
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

Sample Output

4

Hint

Source

Orange