题目描述

很少人知道其实奶牛非常喜欢到洞穴里面去探险。

洞窟里有 $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$ 行每行三个整数，表示一条双向通道的起点终点和宽度阈值。

输出格式

最多能吃掉的干草数。

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

4