C. Сложная загадка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Василий очень любит разные загадки. Сегодня он нашёл загадку, которую не смог решить сам, поэтому он просит вас помочь ему.

У Василия есть n строк, состоящих из строчных букв английского алфавита. Он хочет, чтобы строки располагались в лексикографическом порядке (как в словаре), но при этом не хочет менять их местами. Единственное, что Василий может делать, это разворачивать строки (первая буква становится последней, вторая предпоследней и так далее).

Чтобы развернуть i-ю строку Василию, надо потратить ci единиц энергии. Василия интересует минимальное количество энергии, которое необходимо потратить, чтобы строки шли в лексикографическом порядке.

Строка A лексикографически меньше строки B, если она короче B (|A| < |B|) и является её префиксом, либо ни одна из них не является префиксом другой, и в первой позиции, где они различаются, в строке A стоит символ с меньшим номером.

В данной задаче две одинаковые строки на соседних позициях не нарушают порядок лексикографической сортировки.

Входные данные

В первой строке входных данных записано единственное целое число n (2 ≤ n ≤ 100 000) — количество строк.

Во второй строке записаны n целых чисел ci (0 ≤ ci ≤ 109), i-е из которых равняется количеству энергии, необходимому Василию для разворота i-й строки.

Далее следуют n строк, состоящих из строчных букв английского алфавита. Суммарная длина всех строк не превышает 100 000.

Выходные данные

Если, разворачивая какие-либо из данных строк, невозможно добиться, чтобы они следовали в лексикографическом порядке, то выведите  - 1. В противном случае выведите минимальное количество энергии, которое придётся потратить Василию.

Примеры
Входные данные
2
1 2
ba
ac
Выходные данные
1
Входные данные
3
1 3 1
aa
ba
ac
Выходные данные
1
Входные данные
2
5 5
bbb
aaa
Выходные данные
-1
Входные данные
2
3 3
aaa
aa
Выходные данные
-1
Примечание

Во втором примере можно развернуть строку 2 или строку 3. На разворот строки 3 тратится меньше энергии, поэтому правильным ответом будет развернуть её. В третьем примере обе строки не изменяются после разворота и расположены в неправильном порядке, поэтому ответом является  - 1. В четвёртом примере обе строки состоят из букв «a», но в отсортированном порядке строка «aa» должна располагаться раньше строки «aaa», поэтому ответ  - 1.