AT_jsc2026_final_d Debt Cancellation

長さ $ N $ の整数列 $ a=(a_1,a_2,\ldots,a_N) $ があります。 はじめ、 $ a=(0,0,\ldots,0) $ です。 $ Q $ 回の更新を順に行います。 $ i $ 回目の更新では、全ての $ j=1,2,\ldots,N $ について $ a_j $ に $ X_{i,j} $ を加えます。 各更新について、 $ N $ 個の加算を全て行った直後に、以下の**帳消し操作**を $ 1 $ 回行うかどうかを選べます。 - 全ての $ j=1,2,\ldots,N $ について、 $ a_j $ を $ \max(a_j,0) $ に置き換える。 整数 $ M $ が与えられます。 各 $ k=1,2,\ldots,M $ について、帳消し操作をちょうど $ k $ 回行うとき、最終的な $ \sum_{i=1}^N a_i $ としてあり得る最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ M $ $ X_{1,1} $ $ X_{1,2} $ $ \ldots $ $ X_{1,N} $ $ X_{2,1} $ $ X_{2,2} $ $ \ldots $ $ X_{2,N} $ $ \vdots $ $ X_{Q,1} $ $ X_{Q,2} $ $ \ldots $ $ X_{Q,N} $

各 $ k=1,2,\ldots,M $ に対する答えを、この順に空白区切りで出力せよ。

### Sample Explanation 1 $ k=1 $ のとき、 $ 2 $ 回目の更新の直後に帳消し操作を行います。このとき、 $ a $ は以下のように変化します。 - $ 1 $ 回目の更新後： $ a=(-2,5,-1) $ となる - $ 2 $ 回目の更新後： $ a=(-5,2,-7) $ となり、ここで帳消し操作を行い $ a=(0,2,0) $ となる - $ 3 $ 回目の更新後： $ a=(5,4,-1) $ となる - $ 4 $ 回目の更新後： $ a=(-2,8,4) $ となる 最終的な $ \sum_{i=1}^N a_i $ は $ 10 $ になります。 $ k=2 $ のときは、 $ 3,4 $ 回目の更新の直後に帳消し操作を行うのが最適です。 ### Constraints - $ 1 \le N \le 10 $ - $ 1 \le Q \le 10^4 $ - $ 1 \le M \le \min(Q,1000) $ - $ -10^9 \le X_{i,j} \le 10^9 $ - 入力される値は全て整数