보석 게임

djangg7과 ibasic은 광산에서 보석을 캐는 광부이다. 광산은 지하 $1$층부터 지하 $R$층까지 있다. 이때 $R$은 짝수이다.

광산의 각 층에는 $K$개의 보석이 있다. 지하 $i$층의 $j$번째 보석의 가치는 $s_{i, j}$이다.

두 사람은 작업의 효율을 위해 지하 $1$층부터 지하 $R$층까지 순서대로 방문한다. 지하 $1$층에서는 djangg7이 보석을 캐며, 이후로는 직전 층에서 보석을 캐지 않은 광부가 보석을 캔다.

빠르고 정확한 작업을 위해 한 층에서는 보석을 정확히 하나 캐야 한다. 그런데 지하 $i$층에서 $j$번째 보석을 캐면 지하 $i+1$층의 $j$번째 보석의 보석이 훼손되며, 훼손된 보석의 가치는 $0$이 된다. 지하 $R$층에서 보석을 캘 때는 지하 $R+1$층이 없으므로 아무런 보석도 훼손되지 않는다.

너무 심심했던 djangg7과 ibasic은 각자 채굴한 보석의 가치 합을 비교하여 가치 합이 더 높은 광부가 승리하는 게임을 하기로 했다. 두 광부가 캔 보석의 가치 합이 같은 경우 ibasic이 이긴다.

격차를 최대한 벌리는 것이 좋다고 생각한 두 광부는 모든 보석을 캔 뒤 자신이 캔 보석의 가치 합에서 상대가 캔 보석의 가치 합을 뺀 값을 최대화하는 전략을 사용하기로 했다. 이때 누가 승리하는 지와 두 광부가 캔 보석의 가치 합의 차이를 구하시오.

첫 번째 줄에 광산의 층 수 $R$, 각 층에 있는 보석의 개수 $K$가 공백으로 구분되어 주어진다. $(1 \le R, K \le 2\,000;$ $R$은 짝수$)$

두 번째 줄부터 $R$개의 줄에 걸쳐 각 줄에 각 층에 있는 보석의 가치를 나타내는 $K$개의 정수가 공백으로 구분되어 주어진다. $i+1$번째 줄에는 지하 $i$층에 있는 보석의 가치 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$가 공백으로 구분되어 주어진다. $(-10^9 \le s_{i,j} \le 10^9)$

첫 번째 줄에 게임의 승자와 두 광부가 캔 보석의 가치 합의 차을 공백으로 구분하여 출력한다.