Problem Statement

You are given a connected undirected graph with $N$ vertices and $M$ edges, where the vertices are labeled $1$ to $N$. The graph does not contain self-loops, but it may contain multi-edges. Each edge has a color, and the $i$-th edge has a color $c_i$ ($1 \leq c_i \leq C$) and connects vertices $u_i$ and $v_i$. Also, a sequence $A = (A_1, A_2, \dots, A_C)$ is given.

Among the spanning trees of this graph, those satisfying the following condition are called colorful spanning trees:

• For every integer $i$ such that $1 \leq i \leq C$, the number of edges of color $i$ included in the spanning tree is at most $A_i$.

Find the number of integer pairs $(L, R)$ with $1 \leq L \leq R \leq C$ that satisfy the following condition:

• There exists a colorful spanning tree $T$ such that every edge in $T$ has a color $c$ with $L \leq c \leq R$.

Constraints

• $2 \leq N \leq 150$
• $N - 1 \leq M \leq \min\left(\frac{C N (N-1)}{2}, 5 \times 10^5\right)$
• $1 \leq C \leq 300$
• $1 \leq A_i \leq N-1$
• $\sum_{i=1}^C A_i \leq 300$
• $1 \leq u_i < v_i \leq N$
• $1 \leq c_i \leq C$
• If $i \neq j$, then $(u_i, v_i, c_i) \neq (u_j, v_j, c_j)$
• The given graph is connected.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M C
A_1 A_2 \dots A_C
u_1 v_1 c_1
u_2 v_2 c_2
\vdots
u_M v_M c_M

Output

Print the number of integer pairs $(L, R)$ with $1 \leq L \leq R \leq C$ that satisfy the condition in the problem statement.