F. Үнэтэй тэмдэгт мөрүүд

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

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

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

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

Танд $n$ ширхэг $t_{i}$ тэмдэгт мөрүүд өгчээ.Тэмдэгт мөр бүр $c_{i}$ үнэтэй. гэж тэмдэгт мөрийн функцийг тодорхойлъё.Энд $p_{s, i}$-аар $t_{i}$-д $s$ тэмдэгт мөр хэдэн удаа орсон тоог тэмдэглэх ба $|s|$-аар $s$ тэмдэгт мөрийн уртыг тэмдэглэв.Тэгвэл бүх тэмдэгт мөрүүдийн хувьд $f(s)$ функцийн хамгийн их утгыг олно уу.

Тэмдэглэл: $s$ тэмдэгт мөр нь заавал $t$-ын хэсэг тэмдэгт мөр байх албагүй.

Оролт

Эхний мөрөнд $t$ тэмдэгт мөрүүдийн тоо болох ганц бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) өгөгдөнө.

Дараагийн $n$ мөрийн мөр болгонд Англи жижиг үсгүүд агуулах хоосон биш $t_{i}$ тэмдэгт мөр өгөгдөнө.

Мөн бүх $t$ тэмдэгт мөрүүдийн уртын нийлбэр нь $5*10^{5}$-аас ихгүй байна.

Сүүлийн мөрөнд $n$ ширхэг бүхэл тоо $c_{i}$ ($-10^{7} ≤ c_{i} ≤ 10^{7}$) өгөгдөх ба энэ нь $i$-дахь тэмдэгт мөрийн үнийг илэрхийлнэ.

Гаралт

Бүх тэмдэгт мөр $s$-ын хувьд $f(s)$ функцийн хамгийн их утга болох ганц бүхэл тоо $a$-г хэвлэнэ.

Тэмдэглэл: Дахин хэлэхэд $s$ тэмдэгт мөр нь заавал $t$-ын хэсэг тэмдэгт мөр байх албагүй.

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

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

Оролт
2
aa
bb
2 1
Гаралт
4
Оролт
2
aa
ab
2 1
Гаралт
5
Сэтгэгдлүүдийг ачааллаж байна...