시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 59 25 20 39.216%

문제

소들은 밥을 먹을 때 친구들과 가까이 줄을 선다. 선영이는 소를 N마리 (2 ≤ N ≤ 1,000 가지고 있고, 1번부터 N번까지 번호를 붙였다. 소는 일직선으로 번호 순으로 줄을 서서 밥을 기다린다. 이 때, 두 마리 이상의 소가 같은 위치에 서는 것도 가능하다. 같은 좌표를 갖는 소가 두 마리 이상일 수도 있다.

서로를 좋아하는 소는 특정 거리 이내에 서 있으려고 한다. 그리고 서로를 싫어하는 소는 특정 거리 이상 떨어지려고 한다. 어떤 소들이 서로를 좋아하는지와 두 소가 최대한 떨어질 수 있는 거리가 길이가 ML(1 ≤ ML ≤ 10,000)인 리스트로 주어진다. 다음으로 어떤 소들이 서로를 싫어하는지와 두 소가 최소한 떨어져야 하는 거리가 MD(1 ≤ MD ≤ 10,000) 길이의 리스트로 주어진다.

위 조건을 만족하면서 줄을 서는 것이 가능하다면, 1번 소와 N번 소의 최대 거리를 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 정수 N, ML, MD가 공백으로 구분되어 주어진다.

둘째 줄부터 ML+1번째 줄까지 양의 정수 A, B, D (1 ≤ A < B ≤ N)가 공백으로 구분되어 주어진다. 소 A와 소 B는 최대한 D (1 ≤ D ≤ 1,000,000)만큼 떨어질 수 있다.

ML+2번째 줄부터 ML+MD+1번째 줄까지 양의 정수 A, B, D (1  ≤ A < B ≤ N)이 공백으로 구분되어 주어진다. 소 A와 소 B는 최소한 D (1 ≤ D ≤ 1,000,000)만큼 떨어져 있어야 한다.

출력

첫째 줄에 1번 소와 N번 소의 최대 거리를 출력한다. 줄을 서는 것이 불가능한 경우에는 -1을 출력한다. 1번 소와 N번 소의 최대 거리가 무한대인 경우에는 -2를 출력한다.

예제 입력

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

예제 출력

27

힌트