Farmer John은 Wisconsin에서 가장 단 버터의 비결인 설탕을 발견했다. 목장에 각설탕을 두면 소 $N$마리 ($1\le N\le500$)가 핥아 아주 단 버터를 더 비싸게 팔 수 있다. 물론 추가 돈은 소의 사치품에 쓴다.

FJ는 영리하다. 옛 Pavlov처럼 종소리를 들으면 특정 목장으로 가게 훈련할 수 있음을 안다. 거기에 설탕을 두고 오후 중간에 종을 울려 저녁 착유에서 완벽한 우유를 얻는다.

각 소는 주어진 목장에 있고 혼자일 필요는 없다. 소의 위치와 목장 간 길에서 종을 울릴 때 총 이동 거리를 최소화할 설탕 목장을 찾자. 연결이 충분해 항상 해가 있다.

입력

• 줄 $1$: 공백 구분 정수, 소 수 $N$, 목장 수 $P$ ($2\le P\le800$), 길 수 $C$ ($1\le C\le1{,}450$). 소 번호 $1\ldots N$, 목장 번호 $1\ldots P$는 고유하다.

• 줄 $2\ldots N+1$: 각 줄 정수는 소가 풀을 뜯는 목장. 소 $i$는 줄 $i+1$이다.

• 줄 $N+2\ldots N+C+1$: 공백 구분 정수 세 개, 두 목장과 길의 길이. 양방향으로 가고 각 목장 쌍의 직접 길은 최대 하나다. 앞 두 정수는 $1\ldots P$, 셋째는 $1\ldots225$다.

출력

• 줄 $1$: 설탕 목장으로 가는 소들의 총 거리 최솟값 정수.

예제

입력 1

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

출력 1

8

참고

도식은 연결을 기하학적으로 보여 준다.

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

$4$에 두면 소 $1$은 $3$ 단위, $2$는 $5$, $3$은 $0$을 가서 합계 $8$이다.

문제 출제: Greg Galperin, 2001