[USACO04OPEN] Cave Cows 1

题目描述

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

输入输出格式

输入格式


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

输出格式


最多能吃掉的干草数。

输入输出样例

输入样例 #1

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

输出样例 #1

4