ГУШТЕР, нови страни инвеститор, дошао је у Србију и његова прва бизнис авантура је отварање херпетолошке радње у центру Београда. План пословања је направљен, али је дошло до проблема при избору назива радње.

Менаџери и PR стручњаци ГУШТЕР-а су установили да је важно да логотип изнад улазних врата садржи изабрано име и буде у облику змије: најпре се први ред логотипа чита слева на десно, па се други ред чита здесна на лево, при чему је почетак другог реда на истој позицији као и крај првог реда; трећи ред се чита слева на десно, а почетак трећег реда је на истој позицији као и крај другог реда итд. Логотип може да буде написан у било ком броју редова (чак и једном), докле год сваки ред садржи бар два слова. На пример, реч “hastalavista” може да се напише у облику змије на следећи начин:

hast
 ala
 vista

Нису сви облици змије подједнако добри. Стручњаци су установили да је најпогоднији логотип за дату реч онај који има највећи змија-скор. Змија-скор се дефинише као број (неуређених) парова слова, једно тик изнад другог, која се поклапају. На пример, наведена змија има змија-скор 1: прво и треће слово “а” су једно изнад другог. Међутим, могуће је постићи змија-скор 2 следећом змијом:

   has
ivalat
sta

Људи из ГУШТЕР-а имају предлог за име радње, али не знају како треба да изгледа оптималан логотип. Одлучили да се обрате вама, младим програмерима, не би ли решили проблем и привукли што је могуће више муштерија. Помозите ГУШТЕР-у да заради што је могуће више.

Опис улаза

У првом и једином реду стандардног улаза налази се ниска која представља предлог имена херпетолошке радње. Знаци у овој ниски су мала слова енглеске абецеде.

Опис излаза

У првом и једином реду стандардног излаза исписати један ненегативан цео број: највећи змија-скор који може да се оствари неким змијоликим распоредом предложеног имена.

Пример 1

Улаз

hastalavista

Излаз

2

Објашњење

Пример из текста задатка.

Пример 2

Улаз

anavolimilovana

Излаз

0

Објашњење

Није могуће поставити било који пар истих слова једно тик изнад другог.

Пример 3

Улаз

abccbbcaac

Излаз

6

Објашњење

Оптималан распоред је:

abc
 bc
 bca
  ca

Два пута се слово b налази изнад слова b, три пута се слово c налази изнад слова c, а само једном се a налази изнад слова a, што даје укупан змија-скор 6.

Ограничења

• Знаци ниске су мала слова енглеске абецеде.
• Ниска садржи не више од \(3000\) знакова и не мање од два знака.

Тест примери су подељени у три дисјунктне групе:

• У тест примерима вредним \(30\) поена: Ниска нема више од \(100\) знакова.
• У тест примерима вредним \(20\) поена: Ниска има више од \(100\), а не више од \(500\) знакова.
• У тест примерима вредним \(50\) поена: Без додатних ограничења.