Masala C
Ota Smurfning afsuni
Ota Smurf qishloqni himoya qiluvchi afsun tayyorlamoqchi. Afsun faqat uning matni palindrom bo'lsa ishlaydi.
Afsun matni uzunligi \(n\) bo'lgan \(s\) satridan iborat. Har bir \(i\) uchun, \(s_i\) belgisini boshqa kichik lotin harfiga almashtirish narxi \(c_i\) ta smurf mevaga teng.
Ota Smurfga afsun matnini palindrom qilish uchun kerak bo'ladigan minimal smurf mevalar sonini topishga yordam bering.
Kiruvchi ma'lumotlar:
Birinchi qatorda \(t\) — testlar soni beriladi.
Har bir test quyidagi ko'rinishda beriladi:
Birinchi qatorda \(n\) — afsun matni uzunligi beriladi.
Ikkinchi qatorda uzunligi \(n\) bo'lgan \(s\) satri beriladi.
Uchinchi qatorda \(n\) ta butun son \(c_1,c_2,\ldots,c_n\) beriladi.
Cheklovlar:
\[
1 \le t \le 10^4
\]
\[
1 \le \sum n \le 2 \cdot 10^5
\]
\[
1 \le c_i \le 10^9
\]
\(s\) faqat kichik lotin harflaridan iborat.
Chiquvchi ma'lumotlar:
Har bir test uchun alohida qatorda afsun matnini palindrom qilish uchun kerak bo'ladigan minimal smurf mevalar sonini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 5 abaca 3 10 5 2 7 4 abcd 8 1 4 9 6 abccba 1 2 3 4 5 6 |
2 9 0 |
Izoh:
Birinchi testda faqat \(s_2\) va \(s_4\) belgilar farq qiladi. Ulardan arzonrog'ini almashtirish uchun \(2\) ta smurf meva kerak.
Ikkinchi testda \(s_1\) va \(s_4\), shuningdek \(s_2\) va \(s_3\) juftliklari farq qiladi. Minimal xarajat \(8+1=9\).
Uchinchi testda satr allaqachon palindrom.
Telegram kanalimizga obuna bo'ling