Та энэ бодлогыг бодсоноор 5 оноо авна.

Манао тэмдэгт мөр дээр ажилладаг шинэ үйлдэл зохиосон ба түүнийгээ нугалах гэж нэрлэсэн. Нугалаа бүр дараалласан хос үсгүүдийн хооронд болох ба тэмдэгт мөрийн хоёр дахь хэсгийг тонгоргоод, нугалах үйлдэл хийсэн байршилтай зэрэгцүүлээд эхний хэсгийн дээр байрлуулна. Энэ үйлдлийг ашиглаад Манао тэмдэгт мөрийг нугалах үйлдэл гүйцэтгэхэд байснаас нэг түвшин илүү бүтэцрүү хөрвүүлнэ. Илүү тодорхой ойлгохын тулд доорх жишээнүүдийг харна уу.

Бид нугалах байрлалуудыг '$|$' тэмдэгтээр тэмдэглэнэ. Жишээлбэл "$AB|RACA|DAB|RA$" хэлбэрээр бичигдсэн "$ABRACADABRA$" үгэн дээр гурван удаа нугалах үйлдэл хийнэ гэсэн үг: эхлээд хамгийн зүүн талд байгаа '$B$' ба '$R$' үсгийн хослолийн голд; дараа нь '$A$' ба '$D$' үсгийн голд; тэгээд хамгийн баруун талд байгаа '$B$' ба '$R$' үсгийн хослолийн голд нугалах үйлдэл хийнэ. Доорх зурагт нугалсан тэмдэгт мөрүүдийн жишээг харуулав.

"ABCDEF|GHIJK" |  "A|BCDEFGHIJK" |  "AB|RACA|DAB|RA" |  "X|XXXXX|X|X|XXXXXX"  
               |                 |                   |       XXXXXX  
    KJIHG      |   KJIHGFEDCB    |      AR           |       X  
   ABCDEF      |            A    |     DAB           |       X  
               |                 |     ACAR          |       XXXXX  
               |                 |       AB          |           X

"$ABCD|EFGH|IJ|K$"-н дахин нэг жишээ:

 K  
IJ  
HGFE  
ABCD

Манао нугалсан тэмдэгт мөр бүрийг үсгүүдийн хэд хэдэн босоо шон хэлбэрээр харж болохийг анзаарсан. Жишээлбэл өмнөх жишээнд доороосоо дээш чиглэлтэй "$AHI$", "$BGJK$", "$CF$", ба "$DE$" гэж уншиж болохуйц дөрвөн шон байна. Манао түүнд өгөгдсөн үгэн дээр нугалах үйлдэл хийх замаар үүсгэж болох нэг үсэгнээс бүтсэн хамгийн өндөр шон ямар байх вэ гэж гайхаж байна. Шон нь хоосон зай агуулахгүй ба хамгийн доод түвшнээс эхлэх ёстой. Жишээлбэл дээр буй дөрвөн жишээний хамгийн баруун талын жишээн дээрх шонгууд нь бүгд хүчинтэй биш юм. Учир нь шон бүр нэг бол зай агуулсан, эсвэл хамгийн доод түвшнээс эхлээгүй, эсвэл хоёр нөхцлийг зөрчсөн байна.

Оролт

Оролтонд нэг мөр байх буюу хоосон зай агуулаагүй $n$ урттай тэмдэгт мөр байна $1 ≤ n ≤ 1000$. Тэмдэгт мөрийн бүх үсэг том байна.

Энэ бодлогод дэд бодлогууд байхгүй. Та зөв бодолт явуулбал 5 оноо авна.

Гаралт

Өгөгдсөн тэмдэгт мөрд нугалах үйлдлүүд хийгээд гарч болох нэг үсгээс бүтсэн хамгийн өндөр шонгийн хэмжээг илэрхийлэх нэг бүхэл тоог хэвлэ.

Эхний жишээг авч үзье. Манао доорх бүтцийг үүсгэх "$AB|RACAD|ABRA$" нугалах үйлдлийг хийснээр гурван '$A$' бүхий шонг үүсгэж чадна:

ABRA  
DACAR  
   AB

Хоёр дахь жишээн дээр "$AB|BB|CBDB$" нугалах үйлдлийг хийснээр гурван '$B$' бүхий шонг үүсгэж чадна:

CBDB  
BB  
AB

Мөн Манао гурван '$B$' бүхий шон үүсгэхийн тулд "$ABBBCBDB$" тэмдэгт мөрийн "$AB|B|BCBDB$" нугалах үйлдлийг ч ашиглаж болно:

 BCBDB  
 B  
AB

Гурав дахь жишээн дээр тэмдэгт мөрөнд ямар ч нугалах үйлдэл хийгдэхгүй ба тэмдэгт мөрийг зүгээр нэг мөрөнд хэвлэнэ.