문제
진흥이는 전투 게임을 시작하기에 앞서 아이템을 먼저 배치하려고 한다. 아이템은 1부터 N번까지 번호가 붙여져 있다. 아이템은 일직선 상에 배치가 되며 1번 아이템은 좌표 0에 배치하고, 2번부터 오른쪽으로 가면서 차례대로 N번까지 배치를 한다. 이 때 N번이 오른쪽에 배치될수록 게임을 유리하게 이끌 수 있다. 아이템을 배치하는 원칙은 다음과 같다.
1. 낮은 번호의 아이템이 높은 번호의 아이템보다 오른쪽에 배치될 수 없다. 2. 같은 위치에 연속된 여러 아이템이 배치될 수 있다.
그런데 어떤 아이템들은 서로 일정거리 이내에 있어야만 성능을 발휘할 수 있고, 또 어떤 아이템들은 일정 거리보다 가까이 있으면 둘 다 폭발해 버리고 만다. 모든 아이템들이 폭발하지 않고 제 성능을 발휘하면서 N번 아이템이 최대한 오른쪽에 배치될 수 있도록 프로그램을 작성하고, N번이 배치된 위치의 좌표를 출력하는 프로그램을 작성하시오.
입력
첫 줄에 아이템의 개수 N(1≤N≤1000), 일정 거리내에 있어야 하는 아이템의 쌍의 수 L(1 ≤ L ≤ 10000), 일정거리 이상 떨어져야 하는 쌍의 수 D(1 ≤ D ≤ 10000)가 각각 주어진다.
다음 줄부터 L개의 줄에 거쳐 S, E, T가 입력된다(1 ≤ S , E ≤ N, 1 ≤ T ≤ 100만). 이것은 S번 아이템과 E번 아이템이 T이하의 거리에 배치되어야 한다는 것을 의미한다.
다음 줄부터 D개의 줄에 거쳐 S, E, T가 입력된다(1 ≤ S , E ≤ N, 1 ≤ T ≤100만). 이것은 S번 아이템과 E번 아이템이 T이상의 거리에 배치되어야 한다는 것을 의미한다.
출력
예제
5 3 2
1 2 13
3 5 24
4 1 35
3 2 11
3 4 10
49
로그인해야 코드를 작성할 수 있어요.