djangg7とibasicは、鉱山で宝石を採掘する鉱夫である。鉱山は地下1階から地下$R$階まであり、$R$は偶数である。

鉱山の各階には$K$個の宝石がある。地下$i$階の$j$番目の宝石の価値は$s_{i, j}$である。

二人は作業効率のため、地下1階から地下$R$階まで順番に訪問する。地下1階ではdjangg7が宝石を採掘し、それ以降は直前の階で宝石を採掘しなかった方の鉱夫が宝石を採掘する。

迅速かつ正確な作業のため、各階で正確に1つの宝石を採掘しなければならない。しかし、地下$i$階で$j$番目の宝石を採掘すると、地下$i+1$階の$j$番目の宝石が損傷し、その宝石の価値は$0$になる。地下$R$階で宝石を採掘する際は、地下$R+1$階が存在しないため、どの宝石も損傷しない。

退屈したdjangg7とibasicは、それぞれが採掘した宝石の価値の合計を比較し、合計が高い方が勝利するゲームをすることにした。二人が採掘した宝石の価値の合計が同じ場合、ibasicが勝利する。

差を最大限に広げることが良いと考えた二人は、すべての宝石を採掘した後、自分が採掘した宝石の価値の合計から相手が採掘した宝石の価値の合計を引いた値を最大化する戦略をとることにした。このとき、どちらが勝利するのか、そして二人が採掘した宝石の価値の合計の差を求めよ。

入力

1行目に鉱山の階数 $R$、各階にある宝石の個数 $K$ が空白区切りで与えられる。$(1 \le R, K \le 2\,000;$ $R$は偶数$)$

2行目から$R$行にわたって、各階にある宝石の価値を表す$K$個の整数が空白区切りで与えられる。$i+1$行目には、地下$i$階にある宝石の価値 $s_{i, 1}, s_{i, 2}, \ldots, s_{i, K}$ が空白区切りで与えられる。$(-10^9 \le s_{i,j} \le 10^9)$

出力

1行目にゲームの勝者と、二人が採掘した宝石の価値の合計の差を空白区切りで出力する。

入出力例

入力 1

4 4
1 2 2 2
5 5 4 0
5 1 5 2
3 0 4 3

出力 1

ibasic 1

入力 2

2 5
8 4 7 9 10
-5 -9 -4 -7 -6

出力 2

djangg7 10