34331번 - Last Man Standing 스페셜 저지

당신은 $N$명의 참가자 중 $K$명을 남기는 서바이벌 프로그램을 만들고 있다. $N-K$개의 대결을 통해 최후 생존하는 $K$명을 뽑으려고 한다.

대결은 두 사람끼리 이루어지며, 패배한 쪽은 탈락한다.

서로 다른 두 사람 $i$와 $j$의 대결은 $M_{ij}$의 화제성을 가지고 있다. 대회의 흥행도는 모든 대결의 화제성의 합을 말한다.

당신은 대회의 흥행도를 최대화하기 위해 대결의 결과를 맘대로 정할 것이다.

대회의 흥행도의 최댓값과, 그 때의 대결 순서를 알아내 보자!

첫째 줄에 참가자의 수 $N$, 생존자의 수 $K$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 1\,000)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$와 $j$가 대결하였을 때의 화제성을 나타내는 값 $M_{i1}, M_{i2}, \cdots, M_{iN}$이 공백으로 구분되어 주어진다.

• $ i \ne j $ $:$ $(1 \le M_{ij} \le 1\,000\,000; \ M_{ij} = M_{ji})$
• $ i = j $ $:$ $(M_{ij} = 0)$

주어지는 모든 수는 정수이다.

첫째 줄에 대회의 흥행도의 최댓값을 출력한다.

다음 줄부터 $N-K$개 줄에 걸쳐 $i$번째 대결의 승자와 패자를 공백으로 구분하여 출력한다.