율클라프스쾨프

시간 제한4초메모리 제한1024 MB

요약

N개의 선물 중 서로 다른 것을 K명의 친구에게 하나씩 나눠 줄 때 선호도 합의 최댓값을 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

알네스는 자기 친구 $K$ 명에게 각각 선물 하나씩 사 주려고 한다(지금이 2월이어도 알네스는 여유를 두는 편이다). 그녀가 있는 가게에는 모든 물건이 정확히 하나씩 있다. 물건은 모두 $N$ 개다. 알네스는 친구들을 아주 잘 알아서 누가 무엇을 얼마나 좋아하는지 정확히 안다. 그녀는 모든 $a_{ij}$ 값을 적어 두었다. $a_{ij}$ 는 친구 $i$ 가 선물 $j$ 를 얼마나 좋아하는지를 나타내는 수다.

이제 알네스는 친구들의 기쁨을 최대로 만들고 싶다. 각 친구가 얻는 기쁨, 즉 $a_{ij}$ 의 합이 최대가 되도록 선물을 나눠 주려고 한다. 친구들의 기쁨 합을 최대로 만들려면 어떤 선물을 사야 할까?

입력

첫째 줄에 두 정수 $K$ (친구 수)와 $N$ (선물 수)가 주어진다.

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

출력

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

제한

$1 \le K \le 14$
$1 \le N \le 100 000$

예제1

예제 1
입력
```
2 3
3 6 4
4 7 4
```
예상 출력
```
11
```