Pile The Integer Game

2 secs 1024 MB
matcharate12

問題文


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

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

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

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

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

入力・制約








・全ての に対し

出力


答えを出力せよ。

入出力例


入力例1
4 4
1 2 10 19
7 10 11 13
8 10 13 15
9 18 20 21
出力例1
9

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

・( 周目) プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・( 周目) プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・プレイヤー を書かれたカードを場に出す
・( 週目) プレイヤー を書かれたカードを場に出す

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

提出


Go (1.14)