TT1103 thought that the microwave situation at the University of Waterloo would be better than that at Pierre Elliott Trudeau High School, but he was wrong! Microwaves at the Waterloo MC (Mainland China) building are spread all throughout the building, and of course, there is always a line of students waiting to microwave their lunches.

The MC building contains ~N~ rooms (numbered from ~1~ to ~N~), which are connected by ~M~ two-way corridors. Each corridor is in the form of ~u~ ~v~ ~d~ ~(1 \le u, v \le N, u \ne v)~, specifying that a corridor of length ~d~ meters connects rooms ~u~ and ~v~. For any pair of nodes, there is at most one edge in between them. Additionally, the ~i^\text{th}~ room contains ~m_i~ microwaves.

Because of the unbearable circumstances, TT1103 plots to destroy as many microwaves in the MC as he can! He will use a powerful move called the Atomic Blast, which will instantly vaporize any microwave in any room no greater than ~K~ meters from the room he currently is in. Assume that room dimensions do not count towards this length.

TT1103 can activate his Atomic Blast move up to ~3~ times. What is the largest number of microwaves that he can destroy?

Constraints

For all subtasks:

~1 \le N \le 100~

~0 \le M \le \frac{N(N-1)}{2}~

~0 \le K \le 10^8~

~1 \le d \le 10\,000~

~0 \le m_i \le 100~

Subtask 1 [15%]

~K = 1~

Up to ~5~ rooms contain at least one microwave.

Subtask 2 [35%]

~d = 1~

Up to ~30~ rooms contain at least one microwave.

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line will contain 3 space-separated integers: ~N~, ~M~, and ~K~.

The next line of input will contain ~N~ space-separated integers. The ~i^\text{th}~ integer signifies ~m_i~.

~M~ lines of input follow. Each line represents a corridor in the form of ~u~ ~v~ ~d~.

Output Specification

Output a single integer, the maximum number of microwaves that TT1103 can destroy.

Sample Input

5 5 2
3 2 3 5 1
1 2 2
2 3 3
1 3 4
3 4 3
3 5 5

Sample Output

13

Explanation for Sample Output

TT1103 can use his first Atomic Blast in room 1 in order to destroy all microwaves in rooms 1 and 2. He then can use two more Atomic Blasts to destroy separately all microwaves in rooms 3 and 4.