## TLE '16 Contest 1 P4 - Microwaves Again!

View as PDF

Points: 12 (partial)
Time limit: 3.0s
Python 5.0s
Memory limit: 128M

Author:
Problem type

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

Up to 5 rooms contain at least one microwave.

Up to 30 rooms contain at least one microwave.

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