Sogang Ground

Yeeun plays Sogang Ground, the game everyone is playing right now. In Sogang Ground you drop by parachute into one of several regions, then collect the items lying around and survive. The winner gets a chicken dinner, and Yeeun has never once won one. She decided that item luck was the problem and not her play, so she wrote a program that reports how many items sit in each region. Even so, she could not tell which region to drop into so that her search range covers the most items.

Each region is joined to other regions by roads of length $l$ ($1 \le l \le 15$), and a road can be walked in both directions. The distance between two regions is the smallest total road length over all paths that join them. Yeeun collects the items of every region whose distance from her landing region is at most her search range $m$ ($1 \le m \le 15$). Find the largest number of items Yeeun can collect.

Suppose the field looks like the picture above and Yeeun's search range is 4. The number outside a circle is the region number, the number inside is the item count, and the number on a line is the road length. If Yeeun lands in region 2 she reaches region 1, region 2 where she stands, region 3 and region 5. Region 4 sits at distance $3 + 5 = 8$, which is greater than the search range 4, so she does not get the items of region 4. She collects 23 items, and that is the largest number she can collect on this field.

The first line contains the number of regions $n$ ($1 \le n \le 100$), Yeeun's search range $m$ ($1 \le m \le 15$), and the number of roads $r$ ($1 \le r \le 100$).

The second line contains the item count $t$ ($1 \le t \le 30$) of each region, in order from region 1 to region $n$.

Each of the next $r$ lines contains the region numbers $a$ and $b$ at the two ends of a road and the road length $l$ ($1 \le l \le 15$). A region number is an integer between 1 and $n$, and the two ends of a road are different regions. Several roads may join the same pair of regions, and the regions are not guaranteed to be connected to one another.

Print the largest number of items Yeeun can collect.