행진 대열에 \(N\)개의 부대가 일직선 도로 위에 서 있다. 부대는 대열의 맨 뒤부터 맨 앞까지 \(1\)번부터 \(N\)번까지 번호가 붙어 있다. \(i\)번 부대는 정수 위치 \(x_i\)(미터)에 서며, 행진 순서는 반드시 지켜져야 한다: \(x_1 \le x_2 \le \dots \le x_N\). 여러 부대가 같은 위치에 서 있을 수도 있다.

친한 부대 쌍이 \(M\)개 있다. 친한 부대 \(a\), \(b\) (\(a < b\))는 서로 가까이 있길 원해서 \(x_b - x_a \le c\) 를 만족해야 한다. 라이벌 부대 쌍도 \(P\)개 있다. 라이벌 부대 \(a\), \(b\) (\(a < b\))는 서로 가까이 서기를 거부해서 \(x_b - x_a \ge c\) 를 만족해야 한다.

모든 조건을 만족하면서 맨 앞 부대와 맨 뒤 부대 사이의 거리 \(x_N - x_1\) 이 최대가 되도록 대열을 배치하시오.

첫째 줄에 \(N\), \(M\), \(P\)가 주어진다 (\(2 \le N \le 1000\), \(0 \le M, P\), \(M + P \le 10\,000\)). 다음 \(M\)개의 줄에 친한 부대 쌍 \(a\ b\ c\)가 주어진다 (\(1 \le a < b \le N\), \(1 \le c \le 10^6\)): \(x_b - x_a \le c\). 마지막 \(P\)개의 줄에 라이벌 부대 쌍 \(a\ b\ c\)가 같은 범위로 주어진다: \(x_b - x_a \ge c\).

가능한 \(x_N - x_1\) 의 최댓값을 출력한다. 모든 조건을 만족하는 배치가 존재하지 않으면 -1을, 거리를 얼마든지 크게 만들 수 있으면 -2를 출력한다. 답이 32비트 정수 범위를 넘을 수 있으므로 64비트 정수를 사용하시오.

riseoj 작성

출처 Original