I. IME1000 project
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. G is a mindful visionary who has led the International Merchandising Enterprise (IME) for many years with great success. Now, under the ambitious IME1000 expansion project, he plans to open a new branch in one of the cities across the country.

There are $$$N$$$ cities connected by $$$M$$$ bidirectional roads. The IME headquarters is located in city $$$1$$$, and all other cities (from $$$2$$$ to $$$N$$$) are candidates for the new branch. If IME opens a branch in some city $$$i$$$, Mr. G will profit $$$v_i$$$.

However, travel isn't free. Every road has a tax $$$w_i$$$ charged per traversal. Fortunately, Mr. G is not just a businessman; he's also a master of reputation management. Every time Mr. G successfully enters a new city and pays the road tax, the citizens and local officials admire his discipline and honor. This admiration manifests as 1 unit of reputation. Thus, each taxed road he passes through increases his total reputation by $$$+ 1$$$.

Once his reputation reaches $$$k$$$, he becomes so respected and trusted that now he has the option to deceive the tax collectors and pass through some road without paying any tax at all, or he can decide to continue paying taxes and increase his reputation normally. However, the moment he uses this "reputation bypass," the news of his deception spreads, and trust is lost. Then his total reputation resets to $$$0$$$, and he must start rebuilding it from scratch by paying taxes again.

However, Mr. G's reputation plays a role not only in reducing travel costs but also in expanding his business. He can only open a new IME branch in a city if he arrives there with a reputation of at least $$$k$$$. If his reputation is lower upon arrival, the local officials remain unconvinced of his trustworthiness, and the opportunity is lost.

Your task is to determine which city (among cities $$$2$$$ to $$$N$$$) Mr. G should choose to open the new branch in order to maximize his net profit. The net profit is calculated as the city's profit value $$$v_i$$$ minus the total amount of taxes paid to reach that city from headquarters (city $$$1$$$), using the optimal use of reputation bypasses along the way. If there is no city that Mr. G can reach with a positive net profit and a reputation of at least $$$k$$$, output $$$-1$$$.

Input

The first line contains three integers $$$N$$$, $$$M$$$, and $$$K$$$ ($$$2 \leq N \leq 10^5, 1 \leq M \leq min(10^5,\frac{n \cdot (n-1)}{2}), 1 \leq K \leq 20$$$) — the number of cities, the number of roads, and the required reputation to open a branch.

The second line contains $$$N - 1$$$ integers $$$v_2, v_3, ..., v_N$$$, where $$$v_i$$$ is the profit Mr. G will obtain by opening a branch in city $$$i$$$ ($$$2 \leq i \leq N$$$) ($$$0 \leq v_i \leq 10^9$$$)

Each of the next M lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq N, 1 \leq w_i \leq 10^9$$$) — indicating a bidirectional road between cities $$$u_i$$$ and $$$v_i$$$ with a tax cost of $$$w_i$$$.

Output

Print a single integer — the maximum positive net profit Mr. G can obtain by opening a branch in a city reachable from city $$$1$$$ with reputation $$$\ge K$$$. The net profit is calculated as the city's profit value minus the total tax paid along the path.

If there is no such city, print -1.

Examples
Input
6 9 2
10 10 50 50 50
1 2 3
1 3 10
2 3 6
2 4 9
3 4 6
3 5 15
4 5 5
4 6 4
5 6 8
Output
38
Input
6 9 2
5 5 10 10 10
1 2 3
1 3 10
2 3 6
2 4 9
3 4 6
3 5 15
4 5 5
4 6 4
5 6 8
Output
-1