Mari ちゃんは SNS で見た広告のゲームに興味を持ったので、インストールしてプレイしてみることにしました。

ゲームでは $M$ 本の車線からなる道路が画面手前から奥に伸びており、左から順に車線 $j = 1,2,...,M$ と番号が振られています。
武器を持った兵士の集団である「軍隊」を適切な車線に移動させることで、軍隊の戦力をできるだけ大きくすることがこのゲームの目的です。

軍隊は「人員」を表す変数 $a$ と「武器威力」を表す変数 $b$ の、$2$ つのパラメータを持っています。
現在時刻 $i = 0$ で軍隊は車線 $1$ にいて、人員は $a=1$、武器威力は $b=1$ です。
軍隊は整数 $n$ を用いて $i = n + 0.5$ と表される時刻にのみ、好きな車線に移動させることが可能です。

これから時刻 $i = 1,2,...,N$ に、各車線にゲートまたはタルが流れてきます。
この情報は整数 $A_{i,j}$ で与えられ、次のような意味を持ちます。

• $A_{i,j}\neq0$ のとき、時刻 $i$ において、車線 $j$ に整数 $A_{i,j}$ が書かれたゲートが流れてくることを意味する。
  時刻 $i$ において車線 $j$ に軍隊がいる場合にこのゲートを通ることになり、通ると $a$ に $A_{i,j}$ が加算される。
  つまり、ゲートに書かれた整数の分だけ、軍隊の人員が増減する。
  ゲートを通ったことによって $a\leq0$ となってしまう場合、この時点でゲームオーバーになる。
• $A_{i,j} = 0$ のとき、時刻 $i$ において、車線 $j$ にタルが流れてくることを意味する。
  時刻 $i$ において車線 $j$ に軍隊がいる場合にこのタルを破壊することができ、破壊すると中身のアタッチメントにより、$b$ に $1$ が加算される。
  つまり、軍隊の武器威力が $1$ 増加する。

さて、軍隊の戦力 $X$ は $X = a^2b$ で定義されます。
時刻 $i = N + 1$ における軍隊の戦力 $X$ を最大化してください。ただし、どのように行動しても途中でゲームオーバーになってしまう場合はその旨を報告してください。

なお、制約から出力すべき値が $1.5\times10^{18}$ 以下であることが証明できます。

• 入力は全て整数
• $1\leq N\leq10^5$
• $1\leq M\leq5$
• $|A_{i,j}|\leq100\ (1\leq i\leq N,1\leq j\leq M)$

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($100$ 点)

• $N \leq10$

2. ($200$ 点)

• $N \leq1000$

3. ($400$ 点)

• 追加の制約はない。

入力は以下の形式で標準入力から与えられる。

時刻 $i = N + 1$ における軍隊の戦力 $X$ の最大値を $1$ 行に出力せよ。
ただし、その前にゲームオーバーとなる場合には $-1$ を出力せよ。