E. Cheapest Beautiful Path
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a simple undirected weighted graph consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$. Vertices $$$x_i$$$ and $$$y_i$$$ are connected by an edge with weight $$$w_i$$$ ($$$1 \le i \le m$$$). An integer $$$a_i$$$ is written on the vertex $$$i$$$ ($$$1 \le i \le n$$$).

The cost of a path $$$v_1, v_2, \dots, v_c$$$ (a path is a sequence of vertices where any two consecutive vertices are connected by an edge) is defined as the sum of weights of all edges on that path.

Let's define beauty of a path $$$v_1, v_2, \dots, v_c$$$ as the sum $$$a_{v_1} + a_{v_2} + \cdots + a_{v_c}$$$. We say that a simple path (a path where each vertex of the graph is included at most once) is beautiful if the beauty of this path is divisible by $$$k$$$ without a remainder.

Your task is to find the beautiful path with the smallest possible cost, or report that such a path does not exist.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n \le 10^4$$$; $$$1 \le m \le 10^4$$$; $$$2 \le k \le 6$$$) — the number of vertices in the graph, the number of edges in the graph, and the desired divisor of the path beauty value.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \lt a_i \lt k$$$), where $$$a_i$$$ is the number written on the vertex $$$i$$$.

Then $$$m$$$ lines follow, the $$$i$$$-th of them contain three integers $$$x_i$$$, $$$y_i$$$, and $$$w_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$; $$$1 \le w_i \le 10^9$$$), indicating an edge between vertices $$$x_i$$$ and $$$y_i$$$ with weight $$$w_i$$$. The given graph does not contain self-loops or multiple edges.

Output

Print a single integer — the minimum possible cost of a beautiful path or -1 if there is no such path.

Examples
Input
4 4 3
1 1 2 1
1 2 1
2 3 4
4 3 5
4 1 1
Output
2
Input
2 1 4
2 3
1 2 1
Output
-1