B. Дзигийн дуртай мөрүүд

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

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

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

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

Дзи зөвхөн латин жижиг үсэгнээс бүрдсэн тусгай мөрийн цуглуулгад дуртай. Латин жижиг үсэг $c$ бүрийн утга нь $w_{c}$ гэдгийг тэр мэдэж байгаа. $f(s)$ функцээр $s = s_{1}s_{2}... s_{|s|}$ ($|s|$ бол мөрийн урт) тусгай мөрийн утга илэрхийлэгдэнэ.

Дзид $s$ мөр байна. Тэр үр дүнгийн мөрийн байж болох хамгийн их утгыг олохын тулд мөрөнд $k$ латин жижиг үсгүүдийг оруулахыг хүсэж байгаа. Хамгийн их боломжит утгыг тооцоолоход нь түүнд тусалж чадах уу?

Оролт

Эхний шугаманд мөр төрлийн $s (1 ≤ |s| ≤ 10^{3})$ байна.

Хоёрдугаар шугаманд $k (0 ≤ k ≤ 10^{3})$ бүхэл тоо байна.

Гуравдугаар шугаманд $w_{a}$-с $w_{z}$ хүртэл хорин зургаан бүхэл тоо байна. Тоо бүр сөрөг биш, $1000$-аас хэтрэхгүй байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Дзид байж чадах үр дүнгийн мөрийн хамгийн их боломжтой утга.

Орчуулсан: Даариймаа

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

Оролт
abc
3
1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Гаралт
41

Тэмдэглэл

Энэ жишээнд Дзи "$abcbbc$" олж авч чадна, $утга = 1*1 + 2*2 + 3*2 + 4*2 + 5*2 + 6*2 = 41$.

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