디저트

창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 만족감이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면, 어떤 날에는 '차라리 케이크를 먹는 게 나았지 않았을까' 하는 식이다. 이럴 때 케이크를 다시 먹으면 좋겠지만 창호는 건강을 위해 디저트는 하루에 한 가지만 먹기로 정해 놓았다.

어느 날 창호는 이런 만족감에 패턴이 있다는 것을 알아냈다. 특정 주기마다 n번째 날에 먹는 특정 디저트의 만족감이 정해져 있는 것이다. 창호는 이 사실을 알아내고 최고의 만족감을 느낄 수 있도록 디저트 계획을 짜기 시작했다. 하지만 문제가 하나 있다. 아무리 맛있는 것이라도 계속해서 먹으면 질리게 마련이다. 따라서 디저트를 먹을 때 전날에 먹었던 것과 같은 것을 먹으면 만족감이 반으로 감소한다.

만약 만족감의 패턴이 위와 같다면, 3일 내내 케이크를 먹었을 때의 만족감은 3 + (8 / 2) + (5 / 2) = 9이고, (각 만족도의 소수점 아래는 버린다.) 가장 큰 만족감을 얻을 수 있는 조합은 마카롱-케이크-마카롱으로 2 + 8 + 7 = 17이다.

이러한 패턴이 주어졌을 때, 창호의 만족감의 최댓값을 찾아주자.

첫 번째 줄에 한 주기의 날짜 수 N (1 ≤ N ≤ 100,000), 디저트 종류의 수 M (1 ≤ M ≤ 10)이 정수로 주어진다.

두 번째 줄부터 M개의 줄에 N개의 자연수 Vij (0 ≤ Vij ≤ 100)가 주어진다.

j (2 ≤ j ≤ M + 1)번째 줄의 i (1 ≤ i ≤ N)번째 자연수 Vij는 i번째 날에 (j – 1)번째 디저트의 만족감을 나타낸다.

한 주기마다 얻을 수 있는 만족감의 최댓값을 출력한다.

단, 각 주기의 첫 날의 만족감은 이전 주기의 마지막 날에 영향을 받지 않으며, 하루에 한 가지의 디저트는 반드시 먹는다.