4. Nové PINy pre trezor

Bola jar. Sniežik sa topil, kvietky kvitli, rástli listy. Ale najmä, hovnivále kládli vajíčka. Ale to nie je len tak, naklásť vajíčka a bezstarostne sa zabávať. Treba ich schovať, ukryť pred beštiami. Náš Lajniak Lajko to mal tentokrát obzvlášť obtiažne. Jeho partnerka ho požiadala, aby zohnal trus, v ktorom pod zemou schovajú vajíčka. Tento materiál je nevyhnutný, aby sa larvy mali čím živiť.

Lajko je ale veľmi zábudlivý lajniak, a minulé leto zabudol svoje zásoby trusu vo Firme Korporátnych Slimákov, kde v tom čase brigádoval. Aby ich dostal naspäť, musel by otvoriť svoj starý firemný trezor. Bohužiaľ, zabudol aj svoj PIN. Našťastie, FKS ponúka zmenu PINu, ak si ho niekto zabudol. Tento proces funguje nasledovne:

Firma Korporátnych Slimákov Lajkovi zaradom navrhne \(p\) rôznych PINov, každý o rovnakej dĺžke \(n\). Užívateľ ide zaradom, a keď je na PINe, ktorý sa mu páči, môže si ho zvoliť. Systém ale ponúka aj ďalšiu zmenu, ak si užívateľ chce výber rozmyslieť. Má to ale háčik. Môže si ďalší PIN zvoliť iba ak sa líši v len jednej cifre od toho, ktorý si zvolil naposledy. Takto si užívateľ môže PIN zmeniť koľkokrát len chce, pokiaľ sa každý ďaľší PIN líši v len jednej cifre. Keďže tento systém naprogramovali slimáci, zmena PINu prebieha pomocou operácie, ktorá zmení jednu cifru v PINe o \(1\), buď sa cifra zväčší, alebo zmenší. Keby si Lajko chcel zmeniť PIN \(0000\) na PIN \(0700\), systému by to trvalo \(7\) operácii.

Lajko ako minulý brigádnik vo firme o tomto systéme vie. Je zároveň veľmi citlivý, čo sa týka problémov jeho pamäte. Chce sa teda vyhnúť zmene PINu. Čiže samozrejme sa namiesto toho pokúsi preťažiť slimačí systém menenia PINu tým, že ho donúti vykonať čo najviac operácií pre každú sadu navrhnutých PINov. Keď systém preťaží, určite sa mu trezor otvorí, a dostane sa k svojmu vysnívanému trusu. Pomôžte Lajkovi zistiť, koľko najviac operácií vie od systému v danej sade vynútiť.

Úloha

Dostanete \(p\) rôznych PINov, každý o rovnakej dĺžke \(n\). V PINe môžu byť aj nuly. Jeden PIN si zvolíte ako začiatočný. Následne si môžete vždy PIN zmeniť na ľubovoľný v zozname nasledujúci PIN, pokiaľ sa od toho, čo máte teraz, líši len v jednej cifre. Ak sa líši vo viacerých cifrách, zobrať si ho nemôžete a idete na ďalší navrhnutý PIN. Keď si takto zmeníte PIN, tak podľa toho, o koľko sa dve rozdielne cifry líšia, toľko sa vykoná operácií. Keď sa dostanete na posledný PIN, po ňom si už ďalej PIN meniť nemôžete.

Vašou úlohou bude zistiť, koľko najviac operácií sa dá vykonať pre daný zoznam navrhnutých PINov.

Formát vstupu

Na prvom riadku dostanete číslo \(n\) (\(1 \leq n \leq 6\)) – počet cifier v každom PINe. Na druhom riadku bude číslo \(p\) (\(1 \leq p \leq 100\,000\)) – počet PINov.

Nasleduje \(p\) riadkov, na \(i\)-tom sa nachádza PIN \(p_i\), pričom PIN je ľubovoľná kombinácia cifier \(0\) až \(9\) o dĺžke \(n\).

Formát výstupu

Vypíšte jedno číslo – najväčší možný počet operácií, ktoré sa dajú vykonať.

Príklad

Input:

4
6
8823
2145
2185
3385
4145
4445

Output:

5

Lajko si zvolí \(2145\) ako začiatočný PIN. Od neho sa môže dostať na \(2185\), čo by vykonalo \(4\) operácie, alebo na \(4145\), čo by vykonalo iba \(2\). Lenže sa mu oplatí zvoliť si \(4145\) aj tak, pretože z neho sa vie dostať na \(4445\), čo by dokopy vykonalo \(5\) operácií. Neexistuje iná stratégia, pomocou ktorej by systém vykonal viac, ako \(5\) operácií.

Input:

5
11
00000
60000
00100
10100
60100
10190
10390
61100
20100
10380
20190

Output:

20