E. Тэмдэгт мөр бүтээх

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

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

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

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

Та $t$ тэмдэгт мөр бүтээх хэрэгтэй болсон. Үүний тулд танд $n$ ширхэг тэмдэгт мөр $s_{1}, s_{2}, ..., s_{n}$ байна. $t$ тэмдэгт мөрийг бүтээхэд таныг дээрх тэмдэгт мөрүүд тээр яг $|t|$ ($|t|$ нь $t$ тэмдэгт мөрийн урт) үйлдэл гүйцэтгэхийг зөвшөөрнө. Үйлдэл бүр дараах байдалтай байна:

  1. $s_{1}, s_{2}, ..., s_{n}$ тэмдэгт мөрүүдээс дурын хоосон биш тэмдэгт мөр сонгоно ;
  2. сонгосон тэмдэгт мөрөөс санамсаргүй нэг тэмдэгт сонгоод цаасан дээр бичнэ;
  3. сонгосон тэмдэгт мөрөөс сонгосон тэмдэгтийг устгана.

Таныг тодорхойлогдсон үйлдлийг гүйцэтгэсний дараа $s_{1}, s_{2}, ..., s_{n}$ тэмдэгт мөрүүдийн нийт тэмдэгтүүдийн тоо 1-ээр хорогдоно. Хэрвээ гүйцэтгэгдсэн үйлдлүүдийн дарааллаар цаасан дээр бичигдсэн тэмдэгтүүд $t$ тэмдэгт мөрийг үүсгэх бол бид $t$ тэмдэг мөрийг бүтээнэ.

Энд өөр хязгаарлалтууд ч байгаа. Тэмдэгт мөр $s_{i}$ бүрийн хувьд та $s_{i}$ тэмдэгт мөрөөс устгаж болох тэмдэгтүүдийн хамгийн их тоо буюу $a_{i}$-г мэдэж байна. Мөн та $s_{i}$ тэмдэгт мөрөөс тэмдэгт устгах нь $i$ рублийн өртөгтэй гэдгийг мэдэж байна. Энэ нь $s_{1}$ тэмдэгт мөрөөс тэмдэгт устгах нь ($1$ рубль) хамгийн хямд ба $s_{n}$ тэмдэгт мөрөөс тэмдэгт устгах нь ($n$ рубль) хамгийн үнэтэй гэсэн үг.

Таны ажил бол та $t$ тэмдэгт мөрийг өгөгдсөн дүрмүүдийн дагуу бүтээхэд шаардлагатай хамгийн бага мөнгөний хэмжээг (рубль-р) олох юм. $t$ тэмдэгт мөрийг үүсгэх өртөг нь таны ашигласан үйлдлүүдийн өртгийн нийлбэр байна.

Оролт

Оролтын эхний мөрөнд $s$ тэмдэгт мөр байх буюу таны бүтээх ёстой тэмдэгт мөр байна.

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

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

Гаралт

Та $t$ тэмдэгт мөрийг бүтээхэд шаардлагатай мөнгөний хэмжээг (рубль-р) илэрхийлэх нэг тоог хэвлэ. Хэрвээ ямар нэгэн шийдэл байхгүй бол -1-г хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
bbaze
3
bzb 2
aeb 3
ba 10
Гаралт
8
Оролт
abacaba
4
aba 2
bcc 1
caa 2
bbb 5
Гаралт
18
Оролт
xyz
4
axx 8
za 1
efg 4
t 1
Гаралт
-1

Тэмдэглэл

Жишээнүүдийн тэмдэглэл:

Эхний жишээн дээр та эхний тэмдэгт мөрөөс "$b$" ба "$z$" тэмдэгтүүдийг $1$ рубль-р авах ёстой, хоёрдугаар тэмдэгт мөрөөс "$a$", "$e$" ба "$b$" тэмдэгтүүдийг $2$ рубль-р авна. Ингээд $t$ тэмдэгт мөрийн өртөг нь $2*1 + 3*2 = 8$.

Хоёр дахь жишээн дээр та эхний тэмдэгт мөрөөс хоёр "$a$" тэмдэгтийг $1$ рубль-р авах ба хоёрдугаар тэмдэгт мөрөөс "$c$" тэмдэгтийг $2$ рубль-р авна, гуравдугаар тэмдэгт мөрөөс хоёр "$a$" тэмдэгтийг $3$ рубль-р авна, харин дөрөвдүгээр тэмдэгт мөрөөс хоёр "$b$" тэмдэгтийг $4$ рубль-р авна. Ингээд нийтдээ $t$ тэмдэгт мөрийг $2*1 + 1*2 + 2*3 + 2*4 = 18$ рубль-р бүтээнэ.

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

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