Informatica Online Judge

  부자처럼 보이기 [1942 / 0796]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 3   Total Tried : 4


The Champion of this Problem (C++) : gs16103 - 0ms / 1528byte
My Best Submission (C++) : N/A

[koistudy.net (34th 백윤기)]
Writer ID : [gs16044]

Background

KOI 마을 사람들은 럭셔리 마을, 부자 마을로 소문이 나 있다.
하지만, 사실 그들은 부자처럼 보일 뿐, 가난한 사람들이 많다.
여태껏 이 비밀을 잘 유지해 왔지만, 며칠 후 KOI 방송국에서 밀착 취재를 온다는 소식이 들려왔다.
자칫하면 KOI 마을이 가난하다는 것을 들킬 수 있기 때문에 사람들은 최대한 부자처럼 보이고 싶어한다.

KOI 마을은 다부다처제다. 한 남자가 여러명의 부인을 두고, 한 여자도 여러명의 남편을 둔다.
남편이나 부인이 없는 사람도 있을 수 있다.
남자가 B 명, 여자가 G 명인데, 남자는 1~B 까지, 여자는 1~G 까지 번호가 붙어있다.
부부 끼리는 결혼 반지가 있는데, 반지의 가격은 다양하다.(같을 수도 있다.)
KOI 방송국은 KOI 마을 사람들의 결혼 반지중 가장 싼 반지를 토대로 취재를 한다고 한다.
따라서 KOI 마을 사람들은 가장 싼 반지를 최대한 비싸게 하고 싶어한다.

이를 위해서 취재 당일 사람들을 지정해 그 사람들은 자신의 반지를 동굴에 숨겨놓을 수 있다.
A 라는 사람이 지정되면 A의 모든 반지는 자동으로 동굴에 숨겨진다 .

하지만, 사람들을 너무 지정하면 기자들이 눈치 챌 수 있으므로 최대 C 명의 사람들만 지정할 수 있다.
무조건 C명을 지정할 필요는 없고 그 이하의 사람을 지정해도 상관없다.
반지들을 숨겼을 때 가장 싼 반지의 최대 가격을 출력하자.

Input

첫 줄에 KOI 마을 남자 수 B 와 여자 수 G 가 입력된다. (B, G 는 각각 5이상 100 이하의 자연수)

둘째 줄에 최대로 지정할 수 있는 사람 수 C 가 입력된다. (C 는 min(B-1, G-1) 이하의 자연수)

셋째 줄에 결혼반지의 수 K가 입력된다. (K는 B*G 이하의 자연수)

이어서 K개 줄에 세 수 P, Q, R 이 입력된다. (P는 B 이하, Q는 G 이하, R은 10^18 이하의 자연수)

P 는 남자의 번호, Q 는 여자의 번호, R 은 보석의 가격이다.

Pi = Pj 이면서 Qi = Qj 인 쌍은 절대로 입력되지 않는다.

Output

가장 싼 반지의 최대 가격을 한 줄에 출력한다.
모든 반지를 숨길 수 있으면 최대 가격 대신 -1 을 출력한다.

IO Example

입력 예제 1
7 8
2
10
1 2 6
1 3 2
2 4 8
3 4 9
4 1 4
5 3 1
6 5 2
7 5 1
6 7 5
6 8 7

출력 예제 1
4

설명
3번 여자와 5번 여자를 지정하면 가장 싼 반지의 가격은 4가 된다.


입력 예제 2
7 8
3
10
1 2 6
1 3 2
2 4 8
3 4 9
4 1 4
5 3 1
6 5 2
7 5 1
6 7 5
6 8 7

출력 예제 2
5

설명
3번 여자와 5번 여자, 그리고 4번 남자를 지정하면 가장 싼 반지의 가격은 5가 된다.


입력 예제 3
5 6
2
7
1 2 9
1 3 1
1 4 1
1 5 1
1 6 1
3 2 1
4 2 1


출력 예제 3
-1

설명
1번 남자와 2번 여자를 지정하면 모든 반지를 숨길 수 있다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]