시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)28512210445.022%

문제

외로운 윤제는 고양이를 키우기로 했다.

$N$ 마리의 고양이를 입양하기로 한 윤제는 고양이들에게 리본을 달아주기 위해 $K$ 종류의 리본을 충분히 준비했다. 즉, 각 리본의 개수는 무한하다. 각 고양이마다 리본의 종류에 따라 좋아하는 정도가 다르고, 이를 만족도로 나타낼 수 있다.

고양이들을 번호순으로 한 줄로 세우고 리본을 달아주려고 하는데, 각 고양이는 자신과 이웃한(왼쪽 혹은 오른쪽) 고양이와 같은 종류의 리본을 다는 것을 굉장히 싫어한다. 윤제는 고양이들이 싫어하는 상황을 피하면서 각 고양이의 리본에 대한 만족도의 총합을 극대화하고 싶다.

이 조건을 만족하는 만족도 합의 최댓값을 윤제에게 알려주자.

입력

첫 번째 줄에는 고양이의 수 $N$과 리본 종류의 수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 100, 2 \leq K \leq 10\,000)$

다음 $N$개의 줄에는 각각 $K$개의 정수 $a_{i,1}, \cdots, a_{i,k}$이 공백으로 구분되어 주어진다. $(1 \leq a_{i,j} \leq 10\,000)$ $a_{i,j}$는 $i$번 고양이가 $j$번 리본을 달았을 때의 만족도를 의미한다.

출력

고양이들이 싫어하는 상황을 피하면서 리본을 달아줄 때, 각 고양이의 만족도의 총합의 최댓값을 출력한다.

예제 입력 1

3 3
10 20 30
30 20 10
20 30 10

예제 출력 1

90

1번 고양이에게 3번 리본을, 2번 고양이에게 1번 리본을, 3번 고양이에게 2번 리본을 달아주었다.

예제 입력 2

3 3
10 20 30
10 20 40
10 20 20

예제 출력 2

80

1번 고양이에게 2번 리본을, 2번 고양이에게 3번 리본을, 3번 고양이에게 2번 리본을 달아주었다.