크리스마스 선물 구매

그림: Trogain (cc-by-sa4.0)

착한 Allnäs는 이월인데도 불구하고(여유를 넉넉히 두어야 한다고 믿기 때문이다) 자신의 $K$명의 친구에게 각각 크리스마스 선물 하나씩 사 주려고 한다. 그녀가 있는 가게에는 각 상품이 정확히 하나씩 있다. 상품은 모두 $N$개 있다. Allnäs는 친구들을 매우 잘 안다. 누가 무엇을 얼마나 좋아하는지 정확히 알고 있다. 그녀는 친구 $i$이(가) 선물 $j$을(를) 얼마나 좋아하는지를 나타내는 모든 $a_{ij}$ 값을 목록에 적어 두었다.

이제 Allnäs는 친구들의 기쁨을 최대화하려고 한다. 그녀는 각 친구의 기쁨을 나타내는 값(즉, $a_{ij}$의 값)의 합이 최대가 되도록 친구들에게 선물을 주려고 한다. 친구들의 기쁨의 합을 최대화하려면 어떤 크리스마스 선물을 사야 하는가?

채점

제출한 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

1 | 8 | $K = 2, 1 \le N \le 5000$

2 | 15 | $K = 2, 1 \le N \le 100\,000$

3 | 30 | $1 \le K \le 8, 1 \le N \le 100\,000$

4 | 27 | $1 \le K \le 14, 1 \le N \le 200$

5 | 20 | $1 \le K \le 14, 1 \le N \le 100\,000$

첫 번째 줄에는 친구의 수를 나타내는 정수 $K$와 선물의 수를 나타내는 정수 $N$가 주어진다.

이어지는 $K$개의 줄에는 각각 $N$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $0 \le a_{ij} \le 10^8$이며, 이는 $i$번째 친구가 $j$번째 선물을 받았을 때 얼마나 기뻐하는지를 나타낸다.

친구들의 기쁨의 합의 최댓값을 나타내는 정수 하나를 출력한다.

Allnäs가 친구 1에게 선물 3을(를), 친구 2에게 선물 2을(를) 사 주면 합은 $a_{31} + a_{22} = 4 + 7 = 11$가 되며, 이는 가능한 최댓값이다.