서강그라운드

예은이는 요즘 인기가 많은 게임 서강그라운드를 즐긴다. 서강그라운드는 여러 지역 가운데 한 곳에 낙하산을 타고 내려간 다음, 그 주변에 떨어져 있는 아이템을 모아 살아남는 게임이다. 1등을 하면 치킨을 상으로 주는데, 예은이는 한 번도 치킨을 먹지 못했다. 실력이 아니라 아이템 운이 문제라고 생각한 예은이는 각 지역에 아이템이 몇 개 있는지 알려 주는 프로그램을 만들었다. 그래도 어느 지역에 내려야 수색 범위 안에서 아이템을 가장 많이 모을 수 있는지는 알 수 없었다.

각 지역은 길이가 $l$ ($1 \le l \le 15$)인 길로 다른 지역과 이어져 있고, 이 길은 양방향으로 지나갈 수 있다. 두 지역 사이의 거리는 두 지역을 잇는 경로에 쓰인 길 길이의 합 가운데 최솟값이다. 예은이는 낙하한 지역에서 거리가 수색 범위 $m$ ($1 \le m \le 15$) 이하인 모든 지역의 아이템을 얻는다. 예은이가 얻을 수 있는 아이템의 최대 개수를 구하라.

필드가 위 그림과 같고 예은이의 수색 범위가 4라고 하자. 원 밖의 숫자는 지역 번호, 원 안의 숫자는 아이템 수, 선 위의 숫자는 길의 길이다. 예은이가 2번 지역에 내리면 1번, 자기가 있는 2번, 3번, 5번 지역에 닿는다. 4번 지역까지 가는 거리는 $3 + 5 = 8$이고 이는 수색 범위 4보다 크므로 4번 지역의 아이템은 얻지 못한다. 이때 얻는 아이템은 23개이고, 이 필드에서 얻을 수 있는 최대 개수다.

첫째 줄에 지역의 개수 $n$ ($1 \le n \le 100$), 예은이의 수색 범위 $m$ ($1 \le m \le 15$), 길의 개수 $r$ ($1 \le r \le 100$)이 주어진다.

둘째 줄에 1번 지역부터 $n$번 지역까지 각 지역에 있는 아이템의 수 $t$ ($1 \le t \le 30$)가 차례대로 주어진다.

셋째 줄부터 $r$개의 줄에 길 양 끝 지역의 번호 $a$, $b$와 길의 길이 $l$ ($1 \le l \le 15$)이 주어진다. 지역 번호는 1 이상 $n$ 이하의 정수이고, 한 길의 두 끝 번호는 서로 다르다. 같은 두 지역을 잇는 길이 여러 개 주어질 수 있고, 모든 지역이 서로 이어져 있다는 보장은 없다.

예은이가 얻을 수 있는 아이템의 최대 개수를 출력한다.