問題文

クリスマス当日。$N$ 人の友だちを持つcardrate君は、とあるカードゲームを持ってきました。そのゲームの名前は BSG というらしいです。
今からcardrate君はこのゲームを $N$ 人で遊びます。その際、各プレイヤーに $L$ 枚ずつ、プレイヤー毎のどのカードにおいても異なる整数が一つ一つ書いてあるカードを配ります。厳密にいうと、プレイヤー $i\ (1\le i\le N)$ には $j\ (1\le j\le L)$ 枚目のカードに $A_{i,j}$ が書かれたものが配られます。ただし全ての $i$ に対して $A_{i,1}\ne A_{i,2}\ne ...\ne A_{i,L_i}$ が成り立つような入力が与えられます。

このゲームには何人だけプレイヤーが回ってきたかを表す、ターン数というものがあり、$n$ 人だけプレイヤーが回ってきた後のゲームの状態をターン $n$ と呼びます。
最初のターン (ターン $1$ ) では、プレイヤー $1$ からゲームを始めます。次のターン (ターン $2$ ) ではプレイヤー $2$ 、その次のターン(ターン $3$ )ではプレイヤー $3$、...、ターン $N$ でプレイヤー $N$ となり、ターン $N+1$ ではプレイヤー $1$...と、繰り返しゲームを行います。言い換えると、ターン $n$ ではプレイヤー $(n\ mod\ N)+1$ がゲームを行います。ただし $x\ mod\ y$ は $x$ を $y$ で割ったあまりを表します。

また、カードを出す場所を場と呼ぶことにします。BSG の以下のルールはに従ってゲームをします。

• ターン $i\ (\ge 2)$ の直前のプレイヤー、すなわちターン $i-1$ にゲームを行うプレイヤーと、ターン $i$ にゲームを行うプレイヤーが場に出したカードに書かれた整数をそれぞれ $a,b$ とする。各ターン毎に行うプレイヤーはゲームを続ける度に $a\lt b$ が成り立つようなカードを必ず場に出さなくてはならない。そのようなカードがない場合、このゲームはターン $i-1$ の時点で終了する

このゲームができるだけ長く続くように各プレイヤーがカードを場に出すとき、ターン数は最大でいくつとなりますか？すなわちこのゲームが最大で何回だけ続けることができるかを求めてください。

入力・制約

・$2\le N\le 10^3$
・$1\le L\le 10^3$
・全ての $i$ に対し $1\le A_{i,1}\lt A_{i,2}\lt …\lt A_{i,L}\le 10^9$

出力

答えを出力せよ。

入出力例

4 4
1 2 10 19
7 10 11 13
8 10 13 15
9 18 20 21

9

次のようにゲームを進めることで、最大で $9$ 回だけ続けることが可能です:

・($1$ 周目) プレイヤー $1$ が $1$ を書かれたカードを場に出す
・プレイヤー $2$ が $7$ を書かれたカードを場に出す
・プレイヤー $3$ が $8$ を書かれたカードを場に出す
・プレイヤー $4$ が $9$ を書かれたカードを場に出す
・($2$ 周目) プレイヤー $1$ が $10$ を書かれたカードを場に出す
・プレイヤー $2$ が $11$ を書かれたカードを場に出す
・プレイヤー $3$ が $13$ を書かれたカードを場に出す
・プレイヤー $4$ が $18$ を書かれたカードを場に出す
・($3$ 週目) プレイヤー $1$ が $19$ を書かれたカードを場に出す

$10$ 回目のゲームでプレイヤー $2$ は場に出せないので $9$ を出力します。