Problem Description

Few people know that cows actually really like exploring caves.

There are $N$ ( $1 \leq N \leq 100$ ) chambers in the cave, connected by $M$ ( $1 \leq M \leq 1000$ ) bidirectional passages. Between any pair of chambers, there is at most one bidirectional passage. There are $K$ ( $1 \leq K \leq 14$ ) chambers, each containing one bale of hay. Every time a cow eats one bale of hay, her weight index increases by $1$.

The greedy Bessie wants to explore the cave and hopes to eat as much hay as possible, but each passage has a width threshold: if her weight index exceeds the corresponding threshold, Bessie will get stuck.

She starts from chamber $1$ with weight index $0$. After wandering around in the cave, she must return to chamber $1$.

What is the maximum number of hay bales she can eat? Note that when Bessie passes through a chamber, she does not have to eat the hay in it.

Input Format

The first line contains $N, M, K$.

The next $K$ lines each contain one integer, indicating a chamber that contains one bale of hay. Then the next $M$ lines each contain three integers, indicating the two endpoints of a bidirectional passage and its width threshold.

Output Format

The maximum number of hay bales that can be eaten.

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

Hint

Translated by ChatGPT 5