28447번 - 마라탕 재료 고르기

하얔이는 마라탕에 여러 재료를 넣어 먹는 것을 좋아한다. 하지만 마라탕에 항상 많은 재료를 넣는다고 맛있는 것은 아니다. 마라탕은 각 재료마다 궁합이 존재해서 같이 넣으면 맛있는 재료도 있고 그렇지 않은 경우도 있다. 여기서 하얔이는 고민에 빠졌다.

대체 어떻게 해야 $K$개의 재료를 넣었을 때 마라탕의 맛을 최대로 할 수 있는거지?

$C_{i, j}$를 재료 $i$와 재료 $j$를 같이 넣었을 때의 궁합이라 하자. 마라탕의 맛은 마라탕에 들어간 모든 재료 쌍의 궁합의 합이다. 고른 재료의 그룹을 $G$라고 했을 때 마라탕의 맛을 수식으로 표현하면 다음과 같다.

$$\sum_{i, j\in G,\ i < j}C_{i,j}$$

가여운 하얔이를 위해 재료를 $K$개만 사용했을 때의 최대의 마라탕의 맛을 구해보자.

첫째 줄에 마라탕 재료의 수 $N (1 \leq N \leq 10)$, 고를 재료의 수 $K (1 \leq K \leq N)$가 공백으로 구분되어 주어진다.

이후, $N$개의 줄에 걸쳐 $i+1$번 줄에 재료 $i$와 다른 재료들의 궁합을 나타내는 수열 ${C_{i, 1}, C_{i, 2}, ..., C_{i,N}}$이 공백으로 구분되어 정수로 주어진다. $(-1\,000 \leq C_{i,j} \leq 1\,000)$ 단, $(C_{i, i} = 0; C_{i, j} = C_{j, i})$

첫째 줄에 $K$개의 재료만 사용한 마라탕의 맛의 최댓값을 출력한다.