소는 먹이 줄에서 친구 가까이 섭니다. John의 $N$소($2\le N\le1{,}000$), 번호 $1..N$는 직선에 번호순이며 밀쳐 여러 소가 같은 위치 좌표일 수 있습니다.

친한 소는 최대 거리, 싫은 소는 최소 거리를 원합니다. $ML$($1\le ML\le10{,}000$) 친한 제약 최대, 다음 $MD$($1\le MD\le10{,}000$) 싫은 제약 최소입니다.

가능하면 제약 만족하는 1과 $N$ 최대 거리를 구하세요.

입력

1행: 공백 구분 정수 $N,ML,MD$.

$2..ML+1$행: 공백 구분 양수 $A,B,D$, $1\le A<B\le N$, 거리 $D$ 이하, $1\le D\le1{,}000{,}000$.

$ML+2..ML+MD+1$행: 공백 구분 양수 $A,B,D$, $1\le A<B\le N$, 거리 $D$ 이상, $1\le D\le1{,}000{,}000$.

출력

1행: 정수, 불가능 $-1$, 1과 $N$ 무한히 멀리 $-2$, 아니면 최대 거리.

예제

입력 1

4 2 1
1 3 10
2 4 20
2 3 3

출력 1

27

참고

참고

예제 설명:

4소, 1과3 최대10, 2와4 최대20, 싫은2와3 최소3.

최적 좌표: 1은0, 2는7, 3은10, 4는27.