题目描述

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

洞窟里有$\red{N(1≤}$$\red{N≤}$$\red{100)}$个洞室，由$\red{M(1≤}$$\red{M≤}$$\red{1000)}$条双向通道连接着它们．每对洞室间至多只有一条双向通道．有$\red{K(1 ≤}$$\red{K≤}$$\red{14)}$个洞室，里面放有$\red{1}$捆干草．牛吃$\red{1}$捆干草，体重指数就会增加$\red{1}$．

贪吃的贝茜要到洞窟里面探险．她希望能吃尽量多的干草，但每条通道有一个宽度阈值，如果体重指数超过相应的阈值，贝茜就会被卡祝她从洞窟$\red{1}$出发，体重指数为$\red{0}$．

在洞里溜达一圈后，她要返回洞窟$\red{1}$． 那她最多能吃多少捆干草呢？注意，贝茜经过一个洞室，不一定非要吃掉里面的干草．

输入格式

第$\red{1}$行输入$\red{N，}$$\red{M，}$$\red{K,}$

之后$\red{K}$行每行一个整数，表示在这个洞室放有一捆干草；

接下来$\red{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