AT_asaporo_a 魔法使い高橋君

[problemUrl]: https://atcoder.jp/contests/cf16-tournament-round2-open/tasks/asaporo_a 高橋君は魔法使いです。高橋君は魔法をかけることで、$ M $ 項からなる数列 $ (a_1,a_2,...,a_M) $ を、$ s_i $ を $ a_1～a_i $ の和とした数列 $ (s_1,s_2,...,s_M) $ に変えることができます。 ある日、高橋君は $ M $ 項からなる数列を $ N $ 個もらい、順番に $ A_1,A_2,...,A_N $ と名付けました。さらに、高橋君は魔法をかけることで、辞書順で比較した際に $ A_1\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_{(1,1)} $ $ A_{(1,2)} $ $ ... $ $ A_{(1,M)} $ $ A_{(2,1)} $ $ A_{(2,2)} $ $ ... $ $ A_{(2,M)} $ $ : $ $ A_{(N,1)} $ $ A_{(N,2)} $ $ ... $ $ A_{(N,M)} $

高橋君がかける魔法の最小回数を出力せよ。ただし、高橋君が目標を達成できないならば、代わりに `-1` を出力せよ。

### 制約 - $ 1\ ≦\ N\ ≦\ 10^3 $ - $ 1\ ≦\ M\ ≦\ 10^3 $ - $ A_i $ の $ j $ 項目を $ A_{(i,j)} $ としたとき、 $ 1\ ≦\ A_{(i,j)}\ ≦\ 10^9 $ ### 部分点 - $ 200 $ 点分のテストケースでは、$ 10^4 $ 回以下の回数で目標を達成し、かつ、どの項も $ 10^9 $ 以下となるようにすることができる。 - 別の $ 800 $ 点分のテストケースでは、$ A_{(i,j)}\ ≦\ 80 $ が成立する。 ### Sample Explanation 1 $ A_2 $ に対して $ 1 $ 回魔法をかけることで、$ A_2\ =\ (2\ ,\ 3\ ,\ 5) $ となり、高橋君は目標を達成できます。 ### Sample Explanation 2 この場合、何回魔法をかけても高橋君は目標を達成できません。