D. Лэжен...

хугацааны хязгаарлалт 6 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Барни Нора-тай хэсэг зуур зугаалсан бөгөөд одоо тэрээр өөрийгөө түүний талаар ямар нэгэн мэдрэмжтэй болсон гэж бодож байгаа юм. Барни түүн уруу гоё захиа явуулахыг хүсэж байгаа бөгөөд түүнийг аль болох аз жаргалтай болгохыг хүсэж байв.

Анхандаа Нора-ын аз жаргалтай байдлын төвшин нь $0$ байна. Нора онцгой үгсэд дуртай бөгөөд жишээлбэл "I'm falling for you" гэх мэтчилэн байх ажээ. Нийтдээ Нора $n$ ширхэг онцгой үг мэдэх бөгөөд тус бүр нь Англи жижиг үсгүүдээс тогтох ба зарим нь хоорондоо ижилхэн байж болох юм(гэвч энэ нь зөвхөн бичих тал дээр ижилхэн байх бөгөөд дуудлага болон утгын хувьд өөр байх юм). Нора Барни-ын бичсэн захианд дараалсан дэд дараалал хэлбэрээр орсон байх өөрийн мэддэг $i$-р онцгой үгийг харах бүрд түүний аз жаргалтай байдлын төвшин $a_{i}$-аар ихэсдэг байв. Эдгээр дэд тэмдэгт мөрүүд нь хоорондоо давхцаж болох бөгөөд жишээлбэл Нора $aaab$ гэсэн захиан дотор $aa$ гэсэн онцгой үгийг 2 удаа $ab$ гэсэн онцгой үгийг 1 удаа олж харах юм.

Захиа бичдэг апп-ын хязгаарлалтаас хамааран Барни зөвхөн $l$ хүртэлх тэмдэгт агуулах захиа бичиж болох байв.

Барни таныг Нораг аль болох аз жаргалтай болгоход туслахыг хүсжээ. Түүнчлэн энэ үйл явцыг бид лэжен... гэж нэрлэх юм.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $l$ ($1 ≤ n ≤ 200, 1 ≤ l ≤ 10^{14}$) өгөгдөх ба эдгээр нь Нора-ын мэдэх онцгой үгсийн тоо болон Барни-ын бичих захианы боломжит хамгийн их уртын хэмжээг тус тус илэрхийлнэ.

2-дахь мөрөнд $n$ ширхэг бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ ($1 ≤ a_{i} ≤ 100$)-ууд өгөгдөх ба эдгээр нь Нора өөрийн мэдэх $i$-р онцгой үгээ харах бүрд түүний аз жаргалтай байдлын төвшин нь $a_{i}$-аар ихэсдэг болохыг илэрхийлэх юм.

Дараагийн $n$ мөрөнд онцгой үгс өгөгдөнө. Эдгээрийн $i$-р мөрөнд зөвхөн Англи жижиг үсгүүдээс тогтох $s_{i}$ гэсэн нэгэн тэмдэгт мөр өгөгдөнө. Эдгээр бүх онцгой үгсийн нийлбэр урт нь $200$-аас хэтрэхгүй байна.

Бүх тэмдэгт мөрүүд нь хоосон биш байна.

Гаралт

Барни-ын захиаг уншсаны дараах Нора-ын аз жаргалтай байдлын төвшний боломжит хамгийн их утгыг илэрхийлэх ганц бүхэл тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3 6
3 2 1
heart
earth
art
Гаралт
6
Оролт
3 6
3 2 8
heart
earth
art
Гаралт
16

Тэмдэглэл

Эхний жишээний оновчтой хариулт нь $hearth$ байх бөгөөд энэ нь бүх онцгой үгсийг яг нэг нэг удаа агуулж байгаа юм.

2-дахь жишээний оновчтой хариулт нь $artart$ байна.

Сэтгэгдлүүдийг ачааллаж байна...