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 rooms (numbered from to ), which are connected by two-way corridors. Each corridor is in the form of , specifying that a corridor of length meters connects rooms and . For any pair of nodes, there is at most one edge in between them. Additionally, the room contains 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 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

In addition, the following subtasks hold additional constraints:

**Subtask 1 [15%]**

Up to 5 rooms contain at least one microwave.

**Subtask 2 [35%]**

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: , , and .

The next line of input will contain space-separated integers. The integer signifies .

lines of input follow. Each line represents a corridor in the form of .

#### 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 Blast*s to destroy separately all microwaves in rooms 3 and 4.

## Comments

The time limit for Java and Python has been raised to 10 seconds. This change should not affect anybody who have submitted in these languages.

UPD: Time limit for other submissions have been raised to 5s. Sorry for any inconvenience.