시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB210705937.107%

문제

소들은 밥을 먹을 때 친구들과 가까이 줄을 선다. 선영이는 소를 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를 출력한다.

예제 입력 1

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

예제 출력 1

27
W3sicHJvYmxlbV9pZCI6IjcwNDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMjUgXHViYTM5XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWI0ZTRcdWM3NDAgXHViYzI1XHVjNzQ0IFx1YmEzOVx1Yzc0NCBcdWI1NGMgXHVjZTVjXHVhZDZjXHViNGU0XHVhY2ZjIFx1YWMwMFx1YWU0Y1x1Yzc3NCBcdWM5MDRcdWM3NDQgXHVjMTIwXHViMmU0LiBcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHVjMThjXHViOTdjIE5cdWI5YzhcdWI5YWMgKDIgJmxlOyZuYnNwO04gJmxlOyAxLDAwMCBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHVhY2UwLCAxXHViYzg4XHViZDgwXHVkMTMwIE5cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHViOTdjIFx1YmQ5OVx1YzYwMFx1YjJlNC4gXHVjMThjXHViMjk0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWJjODhcdWQ2MzggXHVjMjFjXHVjNzNjXHViODVjIFx1YzkwNFx1Yzc0NCBcdWMxMWNcdWMxMWMgXHViYzI1XHVjNzQ0IFx1YWUzMFx1YjJlNFx1YjliMFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWI0NTAgXHViOWM4XHViOWFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxOGNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWMxMWNcdWIyOTQgXHVhYzgzXHViM2M0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWFjMTZcdWIyOTQgXHVjMThjXHVhYzAwIFx1YjQ1MCBcdWI5YzhcdWI5YWMgXHVjNzc0XHVjMGMxXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1Y1x1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMThjXHViMjk0Jm5ic3A7XHVkMmI5XHVjODE1IFx1YWM3MFx1YjlhYyBcdWM3NzRcdWIwYjRcdWM1ZDAgXHVjMTFjIFx1Yzc4OFx1YzczY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWMxMWNcdWI4NWNcdWI5N2MgXHVjMmViXHVjNWI0XHVkNTU4XHViMjk0IFx1YzE4Y1x1YjI5NCZuYnNwO1x1ZDJiOVx1YzgxNSBcdWFjNzBcdWI5YWMgXHVjNzc0XHVjMGMxIFx1YjVhOFx1YzViNFx1YzljMFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVjMTFjXHViODVjXHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NFx1YzljMFx1YzY0MCBcdWI0NTAgXHVjMThjXHVhYzAwIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI1YThcdWM1YjRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVhZTM4XHVjNzc0XHVhYzAwIE1MKDEgJmxlOyBNTCAmbGU7IDEwLDAwMClcdWM3NzggXHViOWFjXHVjMmE0XHVkMmI4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjXHVjNzNjXHViODVjIFx1YzViNFx1YjVhNCBcdWMxOGNcdWI0ZTRcdWM3NzQgXHVjMTFjXHViODVjXHViOTdjIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NFx1YzljMFx1YzY0MCBcdWI0NTAgXHVjMThjXHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyBcdWI1YThcdWM1YjRcdWM4MzhcdWM1N2MgXHVkNTU4XHViMjk0IFx1YWM3MFx1YjlhY1x1YWMwMCBNRCgxICZsZTsgTUQgJmxlOyZuYnNwOzEwLDAwMCkgXHVhZTM4XHVjNzc0XHVjNzU4IFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIFx1YzkwNFx1Yzc0NCBcdWMxMWNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNFx1YmE3NCwgMVx1YmM4OCBcdWMxOGNcdWM2NDAgTlx1YmM4OCBcdWMxOGNcdWM3NTggXHVjZDVjXHViMzAwIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBOLCBNTCwgTURcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTUwrMVx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOCBBLCBCLCBEICgxICZsZTsgQSAmbHQ7IEIgJmxlOyZuYnNwO04pXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxOGMgQVx1YzY0MCBcdWMxOGMgQlx1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgRCAoMSAmbGU7IEQgJmxlOyAxLDAwMCwwMDApXHViOWNjXHVkMDdjIFx1YjVhOFx1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5NTCsyXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNTCtNRCsxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4IEEsIEIsIEQgKDEgJm5ic3A7JmxlOyBBICZsdDsgQiAmbGU7IE4pXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMxOGMgQVx1YzY0MCBcdWMxOGMgQlx1YjI5NCBcdWNkNWNcdWMxOGNcdWQ1NWMgRCAoMSAmbGU7Jm5ic3A7RCAmbGU7IDEsMDAwLDAwMClcdWI5Y2NcdWQwN2MgXHViNWE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCAxXHViYzg4IFx1YzE4Y1x1YzY0MCBOXHViYzg4IFx1YzE4Y1x1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjOTA0XHVjNzQ0IFx1YzExY1x1YjI5NCBcdWFjODNcdWM3NzQgXHViZDg4XHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIDFcdWJjODggXHVjMThjXHVjNjQwIE5cdWJjODggXHVjMThjXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjNzBcdWI5YWNcdWFjMDAgXHViYjM0XHVkNTVjXHViMzAwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCZuYnNwOy0yXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3MDQwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGF5b3V0IiwiZGVzY3JpcHRpb24iOiI8cD5MaWtlIGV2ZXJ5b25lIGVsc2UsIGNvd3MgbGlrZSB0byBzdGFuZCBjbG9zZSB0byB0aGVpciBmcmllbmRzIHdoZW4gcXVldWluZyBmb3IgZmVlZC4gRkogaGFzIE4gKDIgJmx0Oz0gTiAmbHQ7PSAxLDAwMCkgY293cyBudW1iZXJlZCAxLi5OIHN0YW5kaW5nIGFsb25nIGEgc3RyYWlnaHQgbGluZSB3YWl0aW5nIGZvciBmZWVkLiBUaGUgY293cyBhcmUgc3RhbmRpbmcgaW4gdGhlIHNhbWUgb3JkZXIgYXMgdGhleSBhcmUgbnVtYmVyZWQsIGFuZCBzaW5jZSB0aGV5IGNhbiBiZSByYXRoZXIgcHVzaHksIGl0IGlzIHBvc3NpYmxlIHRoYXQgdHdvIG9yIG1vcmUgY293cyBjYW4gbGluZSB1cCBhdCBleGFjdGx5IHRoZSBzYW1lIGxvY2F0aW9uICh0aGF0IGlzLCBpZiB3ZSB0aGluayBvZiBlYWNoIGNvdyBhcyBiZWluZyBsb2NhdGVkIGF0IHNvbWUgY29vcmRpbmF0ZSBvbiBhIG51bWJlciBsaW5lLCB0aGVuIGl0IGlzIHBvc3NpYmxlIGZvciB0d28gb3IgbW9yZSBjb3dzIHRvIHNoYXJlIHRoZSBzYW1lIGNvb3JkaW5hdGUpLjxcL3A+XHJcblxyXG48cD5Tb21lIGNvd3MgbGlrZSBlYWNoIG90aGVyIGFuZCB3YW50IHRvIGJlIHdpdGhpbiBhIGNlcnRhaW4gZGlzdGFuY2Ugb2YgZWFjaCBvdGhlciBpbiBsaW5lLiBTb21lIHJlYWxseSBkaXNsaWtlIGVhY2ggb3RoZXIgYW5kIHdhbnQgdG8gYmUgc2VwYXJhdGVkIGJ5IGF0IGxlYXN0IGEgY2VydGFpbiBkaXN0YW5jZS4gQSBsaXN0IG9mIE1MICgxICZsdDs9IE1MICZsdDs9IDEwLDAwMCkgY29uc3RyYWludHMgZGVzY3JpYmVzIHdoaWNoIGNvd3MgbGlrZSBlYWNoIG90aGVyIGFuZCB0aGUgbWF4aW11bSBkaXN0YW5jZSBieSB3aGljaCB0aGV5IG1heSBiZSBzZXBhcmF0ZWQ7IGEgc3Vic2VxdWVudCBsaXN0IG9mIE1EIGNvbnN0cmFpbnRzICgxICZsdDs9IE1EICZsdDs9IDEwLDAwMCkgdGVsbHMgd2hpY2ggY293cyBkaXNsaWtlIGVhY2ggb3RoZXIgYW5kIHRoZSBtaW5pbXVtIGRpc3RhbmNlIGJ5IHdoaWNoIHRoZXkgbXVzdCBiZSBzZXBhcmF0ZWQuPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIGNvbXB1dGUsIGlmIHBvc3NpYmxlLCB0aGUgbWF4aW11bSBwb3NzaWJsZSBkaXN0YW5jZSBiZXR3ZWVuIGNvdyAxIGFuZCBjb3cgTiB0aGF0IHNhdGlzZmllcyB0aGUgZGlzdGFuY2UgY29uc3RyYWludHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOLCBNTCwgYW5kIE1ELjxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5NTCsxOiBFYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIHBvc2l0aXZlIGludGVnZXJzOiBBLCBCLCBhbmQgRCwgd2l0aCAxICZsdDs9IEEgJmx0OyBCICZsdDs9IE4uIENvd3MgQSBhbmQgQiBtdXN0IGJlIGF0IG1vc3QgRCAoMSAmbHQ7PSBEICZsdDs9IDEsMDAwLDAwMCkgYXBhcnQuPFwvbGk+XHJcblx0PGxpPkxpbmVzIE1MKzIuLk1MK01EKzE6IEVhY2ggbGluZSBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgcG9zaXRpdmUgaW50ZWdlcnM6IEEsIEIsIGFuZCBELCB3aXRoIDEgJmx0Oz0gQSAmbHQ7IEIgJmx0Oz0gTi4gQ293cyBBIGFuZCBCIG11c3QgYmUgYXQgbGVhc3QgRCAoMSAmbHQ7PSBEICZsdDs9IDEsMDAwLDAwMCkgYXBhcnQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlci4gSWYgbm8gbGluZS11cCBpcyBwb3NzaWJsZSwgb3V0cHV0IC0xLiBJZiBjb3dzIDEgYW5kIE4gY2FuIGJlIGFyYml0cmFyaWx5IGZhciBhcGFydCwgb3V0cHV0IC0yLiBPdGhlcndpc2Ugb3V0cHV0IHRoZSBncmVhdGVzdCBwb3NzaWJsZSBkaXN0YW5jZSBiZXR3ZWVuIGNvd3MgMSBhbmQgTi48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2005-2006 Season > USACO December 2005 Contest > Gold 3번

  • 문제를 번역한 사람: arine