문제

한 작업실에는 1번부터 n번까지 번호가 붙은 공명판이 놓여 있다. 각 공명판에는 회수할 수 있는 조각이 일정 개수씩 들어 있다. 공명판들은 r개의 양방향 도선으로 연결되어 있으며, 각 도선에는 신호가 지나가는 데 필요한 길이가 정해져 있다.

기술자는 공명 증폭기를 공명판 하나에만 설치할 수 있다. 증폭기를 설치한 공명판을 기준으로, 도선을 따라 이동했을 때 최단 거리가 m 이하인 모든 공명판의 조각을 한 번씩 회수할 수 있다. 증폭기를 설치한 공명판의 조각도 회수 대상에 포함된다.

증폭기를 어느 공명판에 설치해야 가장 많은 조각을 회수할 수 있는지 계산하여, 회수 가능한 조각 수의 최댓값을 구하시오.

입력

첫째 줄에는 공명판의 개수 n (1 ≤ n ≤ 100), 증폭기의 도달 한계 m (1 ≤ m ≤ 15), 도선의 개수 r (1 ≤ r ≤ 100)이 주어진다.

둘째 줄에는 n개의 숫자가 차례대로 주어진다. i번째 숫자는 i번 공명판에 들어 있는 조각의 수 t (1 ≤ t ≤ 30)를 의미한다.

세 번째 줄부터 r+2번째 줄까지는 도선의 양 끝 공명판 번호 a, b와 도선의 길이 l (1 ≤ l ≤ 15)이 주어진다.

공명판 번호는 1 이상 n 이하의 정수이다. 하나의 도선이 같은 공명판을 양 끝으로 갖는 경우는 없다.

출력

회수할 수 있는 조각 수의 최댓값을 출력한다.

예제 입력 1

5 5 4
5 7 8 2 3
1 4 5
5 2 4
3 2 3
1 2 3

예제 출력 1

23