Vasiliy is fond of solving different tasks. Today he found one he wasn't able to solve himself, so he asks you to help.

Vasiliy is given n strings consisting of lowercase English letters. He wants them to be sorted in lexicographical order (as in the dictionary), but he is not allowed to swap any of them. The only operation he is allowed to do is to reverse any of them (first character becomes last, second becomes one before last and so on).

To reverse the i-th string Vasiliy has to spent c_{i} units of energy. He is interested in the minimum amount of energy he has to spent in order to have strings sorted in lexicographical order.

String A is lexicographically smaller than string B if it is shorter than B (|A| < |B|) and is its prefix, or if none of them is a prefix of the other and at the first position where they differ character in A is smaller than the character in B.

For the purpose of this problem, two equal strings nearby do not break the condition of sequence being sorted lexicographically.


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of strings.

The second line contains n integers c_{i} (0 ≤ c_{i} ≤ 10^9), the i-th of them is equal to the amount of energy Vasiliy has to spent in order to reverse the i-th string. 

Then follow n lines, each containing a string consisting of lowercase English letters. The total length of these strings doesn't exceed 100 000.


-----Output-----

If it is impossible to reverse some of the strings such that they will be located in lexicographical order, print  - 1. Otherwise, print the minimum total amount of energy Vasiliy has to spent.


-----Examples-----
Input
2
1 2
ba
ac

Output
1

Input
3
1 3 1
aa
ba
ac

Output
1

Input
2
5 5
bbb
aaa

Output
-1

Input
2
3 3
aaa
aa

Output
-1



-----Note-----

In the second sample one has to reverse string 2 or string 3. To amount of energy required to reverse the string 3 is smaller.

In the third sample, both strings do not change after reverse and they go in the wrong order, so the answer is  - 1.

In the fourth sample, both strings consists of characters 'a' only, but in the sorted order string "aa" should go before string "aaa", thus the answer is  - 1.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
n = int(input())
c = list(map(int, input().split()))
a = []
for _ in range(n):
	a.append(input())
dp = [[1000000000000000000] * 2 for x in range(200000)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	if a[i - 1] <= a[i] and dp[i - 1][0] < dp[i][0]:
		dp[i][0] = dp[i - 1][0]
	if a[i - 1][::-1] <= a[i] and dp[i - 1][1] < dp[i][0]:
		dp[i][0] = dp[i - 1][1]
	if a[i - 1] <= a[i][::-1] and dp[i - 1][0] + c[i] < dp[i][1]:
		dp[i][1] = dp[i - 1][0] + c[i]
	if a[i - 1][::-1] <= a[i][::-1] and dp[i - 1][1] + c[i] < dp[i][1]:
		dp[i][1] = dp[i - 1][1] + c[i]
if dp[n - 1][0] == 1000000000000000000 and dp[n - 1][1] == 1000000000000000000:
	print(-1)
	return
print(min(dp[n - 1][0], dp[n - 1][1]))


n = int(input())
c = input().split()
c = [int(i) for i in c]
arrofwords = []
for i in range(n):
	s = input()
	arrofwords.append(s)
dp = [[-1 for i in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	x = dp[i - 1][0]
	y = dp[i - 1][1]
	if x == -1 and y == -1:
		dp[i][0] = -1
		dp[i][1] = -1
	elif x == -1:
		o = arrofwords[i - 1]
		if arrofwords[i] >= o[::-1]:
			dp[i][0] = dp[i - 1][1]
		else:
			dp[i][0] = -1
		to = arrofwords[i]
		if to[::-1] >= o[::-1]:
			dp[i][1] = dp[i - 1][1] + c[i]
		else:
			dp[i][1] = -1
	elif y == -1:
		o = arrofwords[i - 1]
		to = arrofwords[i]
		if arrofwords[i] >= o:
			dp[i][0] = dp[i - 1][0]
		else:
			dp[i][0] = -1
		if to[::-1] >= o:
			dp[i][1] = dp[i - 1][0] + c[i]
		else:
			dp[i][1] = -1
	else:
		o = arrofwords[i - 1]
		to = arrofwords[i]
		if arrofwords[i] >= o and arrofwords[i] >= o[::-1]:
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
		elif arrofwords[i] >= o:
			dp[i][0] = dp[i - 1][0]
		elif arrofwords[i] >= o[::-1]:
			dp[i][0] = dp[i - 1][1]
		else:
			dp[i][0] = -1
		if to[::-1] >= o and to[::-1] >= o[::-1]:
			dp[i][1] = min(dp[i - 1][0] + c[i], dp[i - 1][1] + c[i])
		elif to[::-1] >= o:
			dp[i][1] = dp[i - 1][0] + c[i]
		elif to[::-1] >= o[::-1]:
			dp[i][1] = dp[i - 1][1] + c[i]
		else:
			dp[i][1] = -1
if dp[n - 1][0] == -1:
	print(dp[n - 1][1])
elif dp[n - 1][1] == -1:
	print(dp[n - 1][0])
else:
	print(min(dp[n - 1][0], dp[n - 1][1]))


import sys

def read_data():
	n = int(next(sys.stdin))
	prices = list(map(int, next(sys.stdin).split()))
	vocabulary = []
	for i in range(n):
		vocabulary.append(next(sys.stdin).strip())
	return (n, prices, vocabulary)

def apply_op(sNext, sPrev, curCost, optCost):
	if sNext >= sPrev:
		if optCost is None or curCost < optCost:
			return curCost
	return optCost

def solve(n, prices, vocabulary):
	(opt_0, opt_1) = (0, prices[0])
	prevStr = vocabulary[0]
	prevStrReversed = ''.join(reversed(prevStr))
	for (curStr, curPrice) in zip(vocabulary[1:], prices[1:]):
		curStrReversed = ''.join(reversed(curStr))
		(n_opt0, n_opt1) = (None, None)
		if opt_0 is not None:
			n_opt0 = apply_op(curStr, prevStr, opt_0, n_opt0)
			n_opt1 = apply_op(curStrReversed, prevStr, opt_0 + curPrice, n_opt1)
		if opt_1 is not None:
			n_opt0 = apply_op(curStr, prevStrReversed, opt_1, n_opt0)
			n_opt1 = apply_op(curStrReversed, prevStrReversed, opt_1 + curPrice, n_opt1)
		(opt_0, opt_1) = (n_opt0, n_opt1)
		(prevStr, prevStrReversed) = (curStr, curStrReversed)
		if opt_0 is None and opt_1 is None:
			break
	if opt_0 is None:
		return opt_1
	if opt_1 is None:
		return opt_0
	return min(opt_0, opt_1)

def __starting_point():
	(n, prices, vocabulary) = read_data()
	sorting_cost = solve(n, prices, vocabulary)
	if sorting_cost != None:
		print(sorting_cost)
	else:
		print(-1)
__starting_point()


import sys
n = int(input())
a = list(map(int, input().split()))
s = []
r = []
for i in range(0, n):
	x = input()
	s.append(x)
	r.append(x[::-1])
for i in range(0, len(s) - 1):
	if not (s[i] <= s[i + 1] or s[i] <= r[i + 1] or r[i] <= s[i + 1] or (r[i] <= r[i + 1])):
		print(-1)
		sys.exit(0)
dp = [[100000000000000 for _ in range(2)] for _ in range(n)]
dp[-1][0] = 0
dp[-1][1] = a[-1]
flag = 1
for i in range(n - 2, -1, -1):
	if s[i] <= s[i + 1]:
		dp[i][0] = min(dp[i][0], dp[i + 1][0])
	if s[i] <= r[i + 1]:
		dp[i][0] = min(dp[i][0], dp[i + 1][1])
	if r[i] <= s[i + 1]:
		dp[i][1] = min(dp[i][1], dp[i + 1][0] + a[i])
	if r[i] <= r[i + 1]:
		dp[i][1] = min(dp[i][1], dp[i + 1][1] + a[i])
ans = min(dp[0][1], dp[0][0])
if ans == 100000000000000:
	print(-1)
else:
	print(ans)


import math
a = int(input())
z = list(map(int, input().split()))
ans = []
for i in range(a):
	s = input()
	ans.append(s)
dp = [[math.inf for i in range(a)] for i in range(2)]
dp[0][0] = 0
dp[1][0] = z[0]
for i in range(1, len(ans)):
	if ans[i] >= ans[i - 1]:
		dp[0][i] = min(dp[0][i - 1], dp[0][i])
	if ans[i][::-1] >= ans[i - 1]:
		dp[1][i] = min(dp[1][i], dp[0][i - 1] + z[i])
	if ans[i] >= ans[i - 1][::-1]:
		dp[0][i] = min(dp[0][i], dp[1][i - 1])
	if ans[i][::-1] >= ans[i - 1][::-1]:
		dp[1][i] = min(dp[1][i], dp[1][i - 1] + z[i])
x = min(dp[0][-1], dp[1][-1])
if x == math.inf:
	print(-1)
else:
	print(x)


I = lambda : list(map(int, input().split()))
n = I()[0]
c = I()
word = []
for _ in range(n):
	w = input()
	word.append(w)
dp = [[1e+100] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(n - 1):
	if word[i + 1] >= word[i]:
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][0])
	if word[i + 1] >= word[i][::-1]:
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][1])
	if word[i + 1][::-1] >= word[i]:
		dp[i + 1][1] = min(dp[i + 1][1], c[i + 1] + dp[i][0])
	if word[i + 1][::-1] >= word[i][::-1]:
		dp[i + 1][1] = min(dp[i + 1][1], c[i + 1] + dp[i][1])
if min(dp[-1]) < 1e+100:
	print(min(dp[-1]))
else:
	print(-1)


n = int(input())
arr = list(map(int, input().split()))
(prev_s, prev_rev_s) = ('', '')
(res1, res2) = (0, 0)
for i in range(n):
	s = input()
	rev_s = s[::-1]
	(curr_res1, curr_res2) = (1 << 63, 1 << 63)
	if s >= prev_s:
		curr_res1 = res1
	if s >= prev_rev_s:
		curr_res1 = min(curr_res1, res2)
	if rev_s >= prev_s:
		curr_res2 = res1 + arr[i]
	if rev_s >= prev_rev_s:
		curr_res2 = min(curr_res2, res2 + arr[i])
	prev_s = s
	prev_rev_s = rev_s
	res1 = curr_res1
	res2 = curr_res2
print(-1 if min(res1, res2) == 1 << 63 else min(res1, res2))


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
Neo = lambda : list(map(int, input().split()))
(n,) = Neo()
c = Neo()
pw = input()
prw = pw[::-1]
r = [0, c[0]]
inf = float('inf')
for i in range(1, n):
	w = input()
	rw = w[::-1]
	ro = inf
	rro = inf
	if w >= pw:
		ro = min(r[0], ro)
	if w >= prw:
		ro = min(r[1], ro)
	if rw >= pw:
		rro = min(r[0], rro)
	if rw >= prw:
		rro = min(r[1], rro)
	r = [ro, rro + c[i]]
	(pw, prw) = (w, rw)
r = min(r)
if r < inf:
	print(r)
else:
	print(-1)


n = int(input())
ct = list(map(int, input().split()))
prev = ''
a = r_a = 0
for i in range(n):
	c = input()
	x = y = 10 ** 15
	if c >= prev:
		x = a
	if c >= prev[::-1]:
		x = min(x, r_a)
	if c[::-1] >= prev:
		y = a + ct[i]
	if c[::-1] >= prev[::-1]:
		y = min(y, r_a + ct[i])
	a = x
	r_a = y
	prev = c
ans = min(a, r_a)
if ans == 10 ** 15:
	print(-1)
else:
	print(ans)


n = int(input())
ref = [int(x) for x in input().split()]
state = [[float('inf')] * 2 for x in range(n)]
prev = input()
state[0][0] = 0
state[0][1] = ref[0]
flag = 0
for i in range(1, n):
	cur = input()
	if cur >= prev:
		state[i][0] = min(state[i][0], state[i - 1][0])
	if cur >= prev[-1::-1]:
		state[i][0] = min(state[i][0], state[i - 1][1])
	if cur[-1::-1] >= prev:
		state[i][1] = min(state[i][1], state[i - 1][0] + ref[i])
	if cur[-1::-1] >= prev[-1::-1]:
		state[i][1] = min(state[i][1], state[i - 1][1] + ref[i])
	prev = cur
	if state[i][0] >= float('inf') and state[i][1] >= float('inf'):
		flag = 1
		break
if flag == 1:
	print(-1)
else:
	print(min(state[n - 1][0], state[n - 1][1]))


inf = float('inf')
n = int(input())
c = list(map(int, input().split()))
a = [input() for i in range(n)]
dp = [[inf, inf] for i in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	dp[i][0] = min(dp[i - 1][0] if a[i] >= a[i - 1] else inf, dp[i - 1][1] if a[i] >= a[i - 1][::-1] else inf)
	dp[i][1] = min(dp[i - 1][0] + c[i] if a[i][::-1] >= a[i - 1] else inf, dp[i - 1][1] + c[i] if a[i][::-1] >= a[i - 1][::-1] else inf)
ans = min(dp[-1])
print(-1 if ans == inf else ans)


n = int(input())
c = [int(x) for x in input().split()]
sumc = [0, 0]
lastWord = ['', '']
t = [True, True]
newT = [True, True]
newSumc = [0, 0]
for i in range(n):
	s1 = input()
	s = s1
	if (t[0] and s >= lastWord[0]) and (t[1] and s >= lastWord[1]):
		newSumc[0] = min(sumc[1], sumc[0])
		newT[0] = True
	elif t[0] and s >= lastWord[0]:
		newSumc[0] = sumc[0]
		newT[0] = True
	elif t[1] and s >= lastWord[1]:
		newSumc[0] = sumc[1]
		newT[0] = True
	else:
		newT[0] = False
	s2 = s1[::-1]
	s = s2
	if t[0] and s >= lastWord[0]:
		if t[1] and s >= lastWord[1]:
			newSumc[1] = min(sumc[0], sumc[1]) + c[i]
		else:
			newSumc[1] = sumc[0] + c[i]
		newT[1] = True
	elif t[1] and s >= lastWord[1]:
		newSumc[1] = sumc[1] + c[i]
		newT[1] = True
	else:
		newT[1] = False
	lastWord = [s1, s2]
	t[0] = newT[0]
	t[1] = newT[1]
	sumc[0] = newSumc[0]
	sumc[1] = newSumc[1]
	if not (t[0] or t[1]):
		print(-1)
		return
if t[0] and t[1]:
	print(min(sumc[0], sumc[1]))
elif t[0]:
	print(sumc[0])
elif t[1]:
	print(sumc[1])


n = int(input())
c = list(map(int, input().split()))
dp = [[0] * 2 for i in range(n + 1)]
st = [['', '']]
for i in range(1, n + 1):
	s = input()
	st.append([s, s[::-1]])
	for j in range(2):
		dp[i][j] = 1e+18
		for k in range(2):
			if st[i][j] >= st[i - 1][k]:
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + c[i - 1] * j)
ans = min(dp[n][0], dp[n][1])
if ans >= 1e+18:
	print(-1)
else:
	print(min(dp[n][0], dp[n][1]))


import sys
sys.setrecursionlimit(250000)
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
n = int(input())
a = list(map(int, input().split()))
s = []
si = []
for i in range(n):
	s.append(input().strip())
	si.append(s[i][::-1])
import functools
dp = [[-1] * 2 for i in range(n + 1)]

@bootstrap
def rec(i, pst):
	if i >= n:
		yield 0
	if dp[i][pst] != -1:
		yield dp[i][pst]
	res = float('inf')
	rev = si[i]
	if i > 0 and rev < s[i - 1] and (s[i] < s[i - 1]) and (rev < si[i - 1]) and (s[i] < si[i - 1]):
		yield float('inf')
	if i == 0:
		res = min(res, (yield rec(i + 1, 0)))
		res = min(res, (yield rec(i + 1, 1)) + a[i])
	if pst:
		if i > 0 and s[i] >= si[i - 1]:
			res = min(res, (yield rec(i + 1, 0)))
		if i > 0 and rev >= si[i - 1]:
			res = min(res, (yield rec(i + 1, 1)) + a[i])
	else:
		if i > 0 and s[i] >= s[i - 1]:
			res = min(res, (yield rec(i + 1, 0)))
		if i > 0 and rev >= s[i - 1]:
			res = min(res, (yield rec(i + 1, 1)) + a[i])
	dp[i][pst] = res
	yield dp[i][pst]
res = rec(0, 0)
print(res if res != float('inf') else -1)


n = int(input())
c = list(map(int, input().split()))
(a, b, d, d1) = (0, 0, '', '')
for i in range(n):
	e = input()
	e1 = e[::-1]
	a1 = b1 = -1
	if b != -1 and e >= d1 and (a1 == -1 or b < a1):
		a1 = b
	if a != -1 and e1 >= d and (b1 == -1 or a + c[i] < b1):
		b1 = a + c[i]
	if a != -1 and e >= d and (a1 == -1 or a < a1):
		a1 = a
	if b != -1 and e1 >= d1 and (b1 == -1 or b + c[i] < b1):
		b1 = b + c[i]
	(a, b, d, d1) = (a1, b1, e, e1)
if a == b == -1:
	print(-1)
elif a != -1 and b != -1:
	print(min(a, b))
else:
	print(max(a, b))


import sys, math, collections
n = int(input())
inf = 10 ** 18
dp = [[inf, inf] for i in range(n)]
p = [int(x) for x in input().split()]
a = [input() for i in range(n)]
ra = [x[::-1] for x in a]
dp[0] = [0, p[0]]
for i in range(1, n):
	if dp[i - 1][0] != -1 and a[i - 1] <= a[i]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if dp[i - 1][1] != -1 and ra[i - 1] <= a[i]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if dp[i - 1][0] != -1 and a[i - 1] <= ra[i]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + p[i])
	if dp[i - 1][1] != -1 and ra[i - 1] <= ra[i]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + p[i])
print(min(dp[n - 1][0], dp[n - 1][1]) if min(dp[n - 1][0], dp[n - 1][1]) != inf else -1)


n = int(input())
c = list(map(int, input().split()))
s = []
for _ in range(n):
	s.append(input())
dp = [[float('inf')] * n for _ in range(2)]
dp[0][0] = 0
dp[1][0] = c[0]
for i in range(1, n):
	for j in range(2):
		cost = float('inf')
		base_cost = 0
		s_ = s[i]
		if j == 1:
			base_cost = c[i]
			s_ = s_[::-1]
		for k in range(2):
			target_cost = dp[k][i - 1]
			target_s = s[i - 1]
			if k == 1:
				target_s = target_s[::-1]
			if target_s <= s_:
				cost = min(cost, base_cost + target_cost)
			else:
				cost = min(cost, float('inf'))
		dp[j][i] = cost
ans = min(dp[0][n - 1], dp[1][n - 1])
if ans == float('inf'):
	print(-1)
else:
	print(ans)


def solve(n):
	dp[0, 0] = 0
	dp[0, 1] = lis[0]
	for i in range(1, n):
		if strings[i] >= strings[i - 1]:
			dp[i, 0] = min(dp[i, 0], dp[i - 1, 0])
		if strings[i] >= reverse[i - 1]:
			dp[i, 0] = min(dp[i, 0], dp[i - 1, 1])
		if reverse[i] >= strings[i - 1]:
			dp[i, 1] = min(dp[i, 1], lis[i] + dp[i - 1, 0])
		if reverse[i] >= reverse[i - 1]:
			dp[i, 1] = min(dp[i, 1], lis[i] + dp[i - 1, 1])
	return min(dp[n - 1, 0], dp[n - 1, 1])
n = int(input())
lis = list(map(int, input().split()))
strings = []
dp = dict()
for i in range(n):
	strings.append(input())
	dp[i, 0] = float('inf')
	dp[i, 1] = float('inf')
reverse = [st[::-1] for st in strings]
ans = solve(n)
if ans == float('inf'):
	print(-1)
else:
	print(ans)


n = int(input())
cost = [int(i) for i in input().split()]
strings = []
for i in range(n):
	s = input()
	strings += [[s, i, 0], [s[::-1], i, cost[i]]]
strings.sort()
costof = [1000000000000000.0 + 1 for _ in range(n)] + [0]
i = n * 2 - 1
while i >= 0:
	strings[i][2] += costof[strings[i][1] + 1]
	costof[strings[i][1]] = min(costof[strings[i][1]], strings[i][2])
	i -= 1
if costof[0] > 1000000000000000.0:
	print(-1)
else:
	print(costof[0])


n = int(input())
s = input()
s1 = s.split()
en = [int(i) for i in s1]
l = []
dp = [[1e+18 for i in range(2)] for j in range(n)]
for i in range(n):
	s = input()
	l.append(s)
dp[0][0] = 0
dp[0][1] = en[0]
for i in range(1, len(l)):
	flag = 0
	if l[i] >= l[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
		flag = 1
	if l[i] >= l[i - 1][::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
		flag = 1
	if l[i][::-1] >= l[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + en[i])
		flag = 1
	if l[i][::-1] >= l[i - 1][::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + en[i])
		flag = 1
	if flag == 0:
		break
if flag == 0:
	print(-1)
elif min(dp[len(l) - 1][0], dp[len(l) - 1][1]) != 1e+18:
	print(min(dp[len(l) - 1][0], dp[len(l) - 1][1]))
else:
	print(-1)


from math import inf
n = int(input())
a = [int(x) for x in input().split()]
s = []
v = []
for i in range(n):
	s.append(list(input().strip()))
for i in range(n):
	v.append(s[i][::-1])
dp = [[inf, inf] for i in range(n)]
dp[0][0] = 0
dp[0][1] = a[0]
for i in range(1, n):
	if s[i] >= v[i - 1]:
		dp[i][0] = min(dp[i - 1][1], dp[i][0])
	if s[i] >= s[i - 1]:
		dp[i][0] = min(dp[i - 1][0], dp[i][0])
	if v[i] >= s[i - 1]:
		dp[i][1] = min(dp[i - 1][0] + a[i], dp[i][1])
	if v[i] >= v[i - 1]:
		dp[i][1] = min(dp[i - 1][1] + a[i], dp[i][1])
print(min(dp[n - 1]) if min(dp[n - 1]) != inf else -1)


n = int(input())
c = list(map(int, input().split()))
s = []
s1 = []
for _ in range(n):
	s.append(input())
dp1 = 0
dp2 = c[0]
s1.append(s[0][::-1])
for i in range(1, n):
	s1.append(s[i][::-1])
	l1 = []
	if dp1 != -1 and s[i] >= s[i - 1]:
		l1.append(dp1)
	if dp2 != -1 and s[i] >= s1[i - 1]:
		l1.append(dp2)
	l2 = []
	if dp1 != -1 and s1[i] >= s[i - 1]:
		l2.append(dp1 + c[i])
	if dp2 != -1 and s1[i] >= s1[i - 1]:
		l2.append(dp2 + c[i])
	if len(l1) != 0:
		dp1 = min(l1)
	else:
		dp1 = -1
	if len(l2) != 0:
		dp2 = min(l2)
	else:
		dp2 = -1
if dp1 == -1 and dp2 == -1:
	print(-1)
if dp1 != -1 and dp2 != -1:
	print(min(dp1, dp2))
if dp1 != -1 and dp2 == -1:
	print(dp1)
if dp1 == -1 and dp2 != -1:
	print(dp2)


import sys
inf = 10 ** 18
n = int(input())
c = [int(x) for x in input().split()]
s = [input() for i in range(n)]
(r, nr) = (c[0], 0)
for i in range(1, n):
	(r1, nr1) = (inf, inf)
	if s[i] >= s[i - 1]:
		nr1 = nr
	if s[i] >= s[i - 1][::-1]:
		nr1 = min(nr1, r)
	if s[i][::-1] >= s[i - 1]:
		r1 = min(r1, nr + c[i])
	if s[i][::-1] >= s[i - 1][::-1]:
		r1 = min(r1, r + c[i])
	if min(r1, nr1) == inf:
		print(-1)
		sys.exit()
	(r, nr) = (r1, nr1)
print(min(r, nr))


import sys
n = int(input())
c = list(map(int, input().split()))
strings = [input() for i in range(n)]
revstrings = [strings[i][::-1] for i in range(n)]
maxc = sum(c) + 1
d = [[maxc, maxc] for i in range(n)]
d[0][0] = 0
d[0][1] = c[0]
for i in range(1, n):
	if strings[i - 1] <= strings[i]:
		d[i][0] = d[i - 1][0]
	if revstrings[i - 1] <= strings[i]:
		d[i][0] = min(d[i][0], d[i - 1][1])
	if strings[i - 1] <= revstrings[i]:
		d[i][1] = d[i - 1][0] + c[i]
	if revstrings[i - 1] <= revstrings[i]:
		d[i][1] = min(d[i][1], d[i - 1][1] + c[i])
result = min(d[n - 1][0], d[n - 1][1])
if result == maxc:
	print(-1)
else:
	print(result)


n = int(input())
cost = [int(x) for x in input().split()]
arr = []
for i in range(n):
	s = input()
	arr.append(s)
dp = [[-1, -1] for i in range(n)]
dp[0][0] = 0
dp[0][1] = cost[0]
for i in range(1, n):
	if dp[i - 1][0] != -1:
		if arr[i] >= arr[i - 1]:
			dp[i][0] = dp[i - 1][0]
	if dp[i - 1][1] != -1:
		if arr[i] >= arr[i - 1][::-1]:
			if dp[i][0] == -1:
				dp[i][0] = dp[i - 1][1]
			else:
				dp[i][0] = min(dp[i][0], dp[i - 1][1])
	s = arr[i][::-1]
	if dp[i - 1][0] != -1:
		if s >= arr[i - 1]:
			dp[i][1] = dp[i - 1][0] + cost[i]
	if dp[i - 1][1] != -1:
		if s >= arr[i - 1][::-1]:
			if dp[i][1] == -1:
				dp[i][1] = dp[i - 1][1] + cost[i]
			else:
				dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i])
if dp[-1][0] == -1 and dp[-1][1] == -1:
	print(-1)
elif dp[-1][0] == -1 or dp[-1][1] == -1:
	print(max(dp[-1][0], dp[-1][1]))
else:
	print(min(dp[-1][0], dp[-1][1]))


n = int(input())
c = list(map(int, input().split()))
s = [''] * n
INF = int(1000000000000000.0)
not_rev = [INF] * n
rev = [INF] * n
for i in range(n):
	s[i] = input()
not_rev[0] = 0
rev[0] = c[0]
for i in range(1, n):
	if s[i - 1] <= s[i]:
		not_rev[i] = min(not_rev[i], not_rev[i - 1])
	if s[i - 1][::-1] <= s[i]:
		not_rev[i] = min(not_rev[i], rev[i - 1])
	if s[i - 1] <= s[i][::-1]:
		rev[i] = min(rev[i], not_rev[i - 1])
	if s[i - 1][::-1] <= s[i][::-1]:
		rev[i] = min(rev[i], rev[i - 1])
	rev[i] += c[i]
print(-1 if min(rev[n - 1], not_rev[n - 1]) == INF else min(rev[n - 1], not_rev[n - 1]))


import sys
line = sys.stdin.readlines()
n = int(line[0])
c = list(map(int, line[1].split()))
no = (0, '')
yes = (0, '')
for i in range(n):
	s = line[i + 2].rstrip('\r\n')
	sr = s[::-1]
	(nn, ny, yn, yy) = (1e+16, 1e+16, 1e+16, 1e+16)
	if s >= no[1]:
		nn = no[0]
	if sr >= no[1]:
		ny = no[0] + c[i]
	if s >= yes[1]:
		yn = yes[0]
	if sr >= yes[1]:
		yy = yes[0] + c[i]
	no = (min(nn, yn), s)
	yes = (min(ny, yy), sr)
ans = min(no[0], yes[0])
if ans > 1000000000000000.0:
	print(-1)
else:
	print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	from math import inf
	n = int(input())
	c = list(map(int, input().split()))
	a = [input().rstrip() for _ in range(n)]
	dp = [[inf, inf] for _ in range(n)]
	dp[0] = [0, c[0]]
	for i in range(1, n):
		if a[i] >= a[i - 1]:
			dp[i][0] = dp[i - 1][0]
		if a[i] >= a[i - 1][::-1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if a[i][::-1] >= a[i - 1]:
			dp[i][1] = dp[i - 1][0] + c[i]
		if a[i][::-1] >= a[i - 1][::-1]:
			dp[i][1] = min(dp[i - 1][1] + c[i], dp[i][1])
	print(min(dp[-1]) if min(dp[-1]) != inf else -1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from math import inf
n = int(input())
c = list(map(int, input().split()))
li = []
for _ in range(n):
	li.append(input())
dp = [[inf for i in range(2)] for j in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	pre = li[i - 1]
	pre_rev = list((x for x in pre))
	pre_rev.reverse()
	pre_rev = ''.join(pre_rev)
	if li[i] >= pre:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if li[i] >= pre_rev:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	pres = list((x for x in li[i]))
	pres.reverse()
	pres = ''.join(pres)
	if pres >= pre:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
	if pres >= pre_rev:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
ans = min(dp[n - 1][0], dp[n - 1][1])
if ans == inf:
	print(-1)
else:
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
forward = []
backward = []
for i in range(n):
	s = input().strip()
	forward.append(s)
	backward.append(s[::-1])
dp = [[10 ** 18] * 2 for i in range(n)]
dp[0][0] = 0
dp[0][1] = a[0]
ok = True
for i in range(1, n):
	if forward[i] >= forward[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if forward[i] >= backward[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if backward[i] >= forward[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + a[i])
	if backward[i] >= backward[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + a[i])
	if dp[i][0] == 10 ** 18 and dp[i][1] == 10 ** 18:
		ok = False
		break
if ok:
	print(min(dp[-1]))
else:
	print(-1)


n = int(input())
c = list(map(int, input().split()))
ver = (0, '')
rev = (0, '')
for i in range(n):
	s = input().rstrip('\r\n')
	r = s[::-1]
	y = 1e+16
	n = 1e+16
	if ver[1] <= s:
		n = ver[0]
	if rev[1] <= s:
		n = min(n, rev[0])
	if ver[1] <= r:
		y = ver[0] + c[i]
	if rev[1] <= r:
		y = min(y, rev[0] + c[i])
	ver = (n, s)
	rev = (y, r)
sol = min(ver[0], rev[0])
if sol < 1000000000000000.0:
	print(sol)
else:
	print(-1)


LO_C = 0
LO_S = 1
HI_C = 2
HI_S = 3

def main():
	n = int(input())
	costs = list([int(x) for x in input().split()])
	memo = list()
	for i in range(n):
		s = input().strip()
		r = s[::-1]
		if s <= r:
			(lo, lo_c, hi, hi_c) = (s, 0, r, costs[i])
		else:
			(lo, lo_c, hi, hi_c) = (r, costs[i], s, 0)
		if not memo:
			memo.append((lo_c, lo, hi_c, hi))
		else:
			if hi >= memo[-1][LO_S]:
				nxt_hi = hi
				if hi < memo[-1][HI_S] or memo[-1][LO_C] <= memo[-1][HI_C]:
					nxt_hi_c = hi_c + memo[-1][LO_C]
				else:
					nxt_hi_c = hi_c + memo[-1][HI_C]
			else:
				return -1
			if lo >= memo[-1][LO_S]:
				nxt_lo = lo
				if lo < memo[-1][HI_S] or memo[-1][LO_C] <= memo[-1][HI_C]:
					nxt_lo_c = lo_c + memo[-1][LO_C]
				else:
					nxt_lo_c = lo_c + memo[-1][HI_C]
			else:
				nxt_lo = nxt_hi
				nxt_lo_c = nxt_hi_c
			memo.append((nxt_lo_c, nxt_lo, nxt_hi_c, nxt_hi))
	return min(memo[-1][LO_C], memo[-1][HI_C])

def __starting_point():
	print(main())
__starting_point()


from sys import stdin, stdout
INF = float('inf')
n = int(stdin.readline())
prices = list(map(int, stdin.readline().split()))
strings = []
for i in range(n):
	strings.append(stdin.readline().strip())
dp = [[INF, INF, INF, INF] for i in range(n)]
for i in range(n - 1):
	if not i:
		if strings[i] <= strings[i + 1]:
			dp[i][0] = 0
		if strings[i][::-1] <= strings[i + 1]:
			dp[i][1] = prices[i]
		if strings[i] <= strings[i + 1][::-1]:
			dp[i][2] = prices[i + 1]
		if strings[i][::-1] <= strings[i + 1][::-1]:
			dp[i][3] = prices[i] + prices[i + 1]
	else:
		if strings[i] <= strings[i + 1]:
			dp[i][0] = min(dp[i - 1][:2])
		if strings[i][::-1] <= strings[i + 1]:
			dp[i][1] = min(dp[i - 1][2:])
		if strings[i] <= strings[i + 1][::-1]:
			dp[i][2] = min(dp[i - 1][:2]) + prices[i + 1]
		if strings[i][::-1] <= strings[i + 1][::-1]:
			dp[i][3] = min(dp[i - 1][2:]) + prices[i + 1]
if min(dp[n - 2]) >= INF:
	stdout.write('-1')
else:
	stdout.write(str(min(dp[n - 2])))


n = int(input())
c = list(map(int, input().split()))
s1 = ''
s2 = ''
INF = 1e+16
c1 = 0
c2 = 0
for i in range(n):
	s = input()
	sr = s[::-1]
	c11 = c1 if s1 <= s else INF
	c21 = c2 if s2 <= s else INF
	c12 = c1 + c[i] if s1 <= sr else INF
	c22 = c2 + c[i] if s2 <= sr else INF
	s1 = s
	s2 = sr
	c1 = min(c11, c21)
	c2 = min(c12, c22)
ans = min(c1, c2)
if ans >= INF:
	print(-1)
else:
	print(ans)


n = int(input())
ci = list(map(int, input().split()))
words = [['', ''] for i in range(n)]
num = 10 ** 15
ans = [[num, num] for i in range(n)]
ans[0] = [0, 0]
flag = 0
for i in range(n):
	words[i][0] = input()
	words[i][1] = words[i][0][::-1]
for i in range(1, n):
	flag = 0
	for j in range(2):
		for z in range(2):
			if words[i][j] >= words[i - 1][z]:
				flag = 2
				ans[i][j] = min(ans[i][j], ans[i - 1][z] + ci[i - 1] * z)
	if flag == 0:
		flag = 1
		break
if flag == 1 or min(ans[-1]) == num:
	print(-1)
elif ans[-1][0] == -1:
	print(ans[-1][1])
elif ans[-1][1] == -1:
	print(ans[-1][1] + ci[-1])
else:
	print(min(ans[-1][0], ans[-1][1] + ci[-1]))


import os, sys, math
from _thread import start_new_thread
from bisect import bisect_right

class pair:

	def __init__(self, a):
		(self.first, self.second) = (a[0], a[1])

def main():
	INF = 10 ** 18
	n = int(input())
	c = list(map(int, input().split()))
	(a, b) = ([], [])
	for i in range(n):
		s = input()
		a.append(s)
		b.append(s[::-1])
	dp = [pair([INF, INF]) for i in range(0, n)]
	(dp[0].first, dp[0].second) = (0, c[0])
	for i in range(1, n):
		dp[i].first = INF
		dp[i].second = INF
		if a[i] >= a[i - 1]:
			dp[i].first = min(dp[i].first, dp[i - 1].first)
		if a[i] >= b[i - 1]:
			dp[i].first = min(dp[i].first, dp[i - 1].second)
		if b[i] >= a[i - 1]:
			dp[i].second = min(dp[i].second, dp[i - 1].first + c[i])
		if b[i] >= b[i - 1]:
			dp[i].second = min(dp[i].second, dp[i - 1].second + c[i])
	res = min(dp[n - 1].first, dp[n - 1].second)
	print([-1, res][res != INF])

def __starting_point():
	return int(main() or 0)
__starting_point()


from sys import stdin, stdout
int_in = lambda : int(stdin.readline())
arr_in = lambda : [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for y in range(rows)]
str_in = lambda : stdin.readline().strip()
out = lambda o: stdout.write('{}\n'.format(o))
arr_out = lambda o: out(' '.join(map(str, o)))
bool_out = lambda o: out('YES' if o else 'NO')
tests = lambda : range(1, int_in() + 1)
case_out = lambda i, o: out('Case #{}: {}'.format(i, o))

def solve(n, c, strings):
	reversed_strings = list(map(lambda x: x[::-1], strings))
	cost_same = 0
	cost_diff = c[0]
	string_same = strings[0]
	string_diff = reversed_strings[0]
	for i in range(1, n):
		local_same = float('inf')
		local_diff = float('inf')
		if string_same <= strings[i]:
			local_same = min(local_same, cost_same)
		if string_diff <= strings[i]:
			local_same = min(local_same, cost_diff)
		if string_same <= reversed_strings[i]:
			local_diff = min(local_diff, cost_same + c[i])
		if string_diff <= reversed_strings[i]:
			local_diff = min((local_diff, cost_diff + c[i]))
		cost_same = local_same
		cost_diff = local_diff
		string_same = strings[i]
		string_diff = reversed_strings[i]
		if cost_same == float('inf') and cost_diff == float('inf'):
			return -1
	return min(cost_same, cost_diff)
n = int_in()
c = arr_in()
strings = [str_in() for x in range(n)]
out(solve(n, c, strings))


import sys
n = int(input())
c = [int(x) for x in input().split()]
s = [x.strip() for x in sys.stdin.readlines()]
r = [x[::-1] for x in s]
h = [[None, None] for _ in range(n)]
h[0][0] = 0
h[0][1] = c[0]
for i in range(1, n):
	(p, q) = (s[i], s[i][::-1])
	if s[i - 1] <= p and h[i - 1][0] is not None:
		h[i][0] = h[i - 1][0]
	if r[i - 1] <= p:
		if h[i - 1][1] is not None and (h[i][0] is None or h[i][0] > h[i - 1][1]):
			h[i][0] = h[i - 1][1]
	if s[i - 1] <= q and h[i - 1][0] is not None:
		h[i][1] = h[i - 1][0] + c[i]
	if r[i - 1] <= q:
		if h[i - 1][1] is not None and (h[i][1] is None or h[i][1] > h[i - 1][1] + c[i]):
			h[i][1] = h[i - 1][1] + c[i]
(p, q) = (h[n - 1][0], h[n - 1][1])
if p is not None and q is not None:
	print(min(p, q))
elif p is not None:
	print(p)
elif q is not None:
	print(q)
else:
	print(-1)


n = int(input())
e = list(map(int, input().split()))
dp = [[0, 0], [0, 0]]
s_prev = input().strip()
dp[0][1] = e[0]
ans = -1
for i in range(n - 1):
	cur_pos = (i + 1) % 2
	prev_pos = i % 2
	s_cur = input().strip()
	(a, b) = (0, 0)
	if dp[prev_pos][0] != -1 and s_prev <= s_cur:
		a = dp[prev_pos][0]
	else:
		a = -1
	if dp[prev_pos][1] != -1 and s_prev[::-1] <= s_cur:
		b = dp[prev_pos][1]
	else:
		b = -1
	if a == -1 and b == -1:
		dp[cur_pos][0] = -1
	elif a == -1:
		dp[cur_pos][0] = b
	elif b == -1:
		dp[cur_pos][0] = a
	else:
		dp[cur_pos][0] = min(a, b)
	if dp[prev_pos][0] != -1 and s_prev <= s_cur[::-1]:
		a = dp[prev_pos][0] + e[i + 1]
	else:
		a = -1
	if dp[prev_pos][1] != -1 and s_prev[::-1] <= s_cur[::-1]:
		b = dp[prev_pos][1] + e[i + 1]
	else:
		b = -1
	if a == -1 and b == -1:
		dp[cur_pos][1] = -1
	elif a == -1:
		dp[cur_pos][1] = b
	elif b == -1:
		dp[cur_pos][1] = a
	else:
		dp[cur_pos][1] = min(a, b)
	s_prev = s_cur
a = dp[(n + 1) % 2][0]
b = dp[(n + 1) % 2][1]
if a == -1 and b == -1:
	print(-1)
elif a == -1:
	print(b)
elif b == -1:
	print(a)
else:
	print(min(a, b))


n = int(input())
c = list(map(int, input().split()))
inf = 10000000000000000
d = [[inf] * 2 for i in range(n)]
prev_s = input().rstrip()
d[0][0] = 0
d[0][1] = c[0]
flag = 0
for i in range(1, n):
	s = input().rstrip()
	if s >= prev_s:
		d[i][0] = min(d[i][0], d[i - 1][0])
	if s >= prev_s[::-1]:
		d[i][0] = min(d[i][0], d[i - 1][1])
	if s[::-1] >= prev_s:
		d[i][1] = min(d[i][1], d[i - 1][0] + c[i])
	if s[::-1] >= prev_s[::-1]:
		d[i][1] = min(d[i][1], d[i - 1][1] + c[i])
	prev_s = s
	if d[i][0] >= inf and d[i][1] >= inf:
		flag = -1
		break
if flag == -1:
	print(-1)
else:
	print(min(d[n - 1][0], d[n - 1][1]))


INF = float('inf')
n = int(input())
s = []
srev = []
cost = list(map(int, input().split()))
for i in range(n):
	c = input()
	s.append(c)
	srev.append(c[::-1])
r = 0
nr = 0
for i in range(1, n):
	if s[i - 1] <= s[i]:
		ss = 0
	else:
		ss = INF
	if s[i - 1] <= srev[i]:
		sr = cost[i]
	else:
		sr = INF
	if srev[i - 1] <= s[i]:
		rs = 0
	else:
		rs = INF
	if srev[i - 1] <= srev[i]:
		rr = cost[i]
	else:
		rr = INF
	if i == 1:
		rs += cost[i - 1]
		rr += cost[i - 1]
	if min([ss, sr, rs, rr]) == INF:
		print(-1)
		break
	(nr, r) = (min(r + rs, ss + nr), min(sr + nr, rr + r))
else:
	res = min(nr, r)
	print(res if res != INF else -1)


import math as m
n = int(input())
cost = list(map(int, input().split()))
s = []
sr = []
for i in range(n):
	s.append(list(input()))
	sr.append(list(reversed(s[i])))
dp = [[0, 0] for i in range(n + 1)]
flag = 0
dp[0][1] = cost[0]
for i in range(1, n):
	if dp[i - 1][0] == -1 and dp[i - 1][1] == -1:
		flag = 1
		break
	elif dp[i - 1][0] != -1 and dp[i - 1][1] == -1:
		if s[i] >= s[i - 1]:
			dp[i][0] = dp[i - 1][0]
		else:
			dp[i][0] = -1
		if sr[i] >= s[i - 1]:
			dp[i][1] = dp[i - 1][0] + cost[i]
		else:
			dp[i][1] = -1
	elif dp[i - 1][0] == -1 and dp[i - 1][1] != -1:
		if s[i] >= sr[i - 1]:
			dp[i][0] = dp[i - 1][1]
		else:
			dp[i][0] = -1
		if sr[i] >= sr[i - 1]:
			dp[i][1] = dp[i - 1][1] + cost[i]
		else:
			dp[i][1] = -1
	else:
		if s[i] >= s[i - 1] and s[i] >= sr[i - 1]:
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
		elif s[i] >= s[i - 1] and s[i] < sr[i - 1]:
			dp[i][0] = dp[i - 1][0]
		elif s[i] < s[i - 1] and s[i] >= sr[i - 1]:
			dp[i][0] = dp[i - 1][1]
		else:
			dp[i][0] = -1
		if sr[i] >= s[i - 1] and sr[i] >= sr[i - 1]:
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + cost[i]
		elif sr[i] >= s[i - 1] and sr[i] < sr[i - 1]:
			dp[i][1] = dp[i - 1][0] + cost[i]
		elif sr[i] < s[i - 1] and sr[i] >= sr[i - 1]:
			dp[i][1] = dp[i - 1][1] + cost[i]
		else:
			dp[i][1] = -1
if flag == 1:
	print(-1)
else:
	res = max(dp[n - 1][0], dp[n - 1][1]) if min(dp[n - 1][0], dp[n - 1][1]) == -1 else min(dp[n - 1][0], dp[n - 1][1])
	print(res)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())
n = mint()
c = list(mints())
prev = minp()
a = 0
b = c[0]
bigg = 4 * 10 ** 18
for i in range(1, n):
	d = bigg
	e = bigg
	next = minp()
	if next >= prev:
		d = min(d, a)
	if next >= prev[::-1]:
		d = min(d, b)
	if next[::-1] >= prev:
		e = min(e, a + c[i])
	if next[::-1] >= prev[::-1]:
		e = min(e, b + c[i])
	(a, b) = (d, e)
	prev = next
a = min(a, b)
if a == bigg:
	print(-1)
else:
	print(a)


I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
n = I()
C = IL()
MAXINT = (1 << 63) - 1
A = [[0, 0]]
S = [['A', 'A']]
for i in range(n):
	s1 = input()
	s2 = s1[::-1]
	S.append([s1, s2])
	A.append([MAXINT, MAXINT])
	if s1 >= S[-2][0]:
		A[-1][0] = min(A[-1][0], A[-2][0])
	if s1 >= S[-2][1]:
		A[-1][0] = min(A[-1][0], A[-2][1])
	if s2 >= S[-2][0]:
		A[-1][1] = min(A[-1][1], A[-2][0] + C[i])
	if s2 >= S[-2][1]:
		A[-1][1] = min(A[-1][1], A[-2][1] + C[i])
print(min(A[-1]) if min(A[-1]) < MAXINT else -1)


n = int(input())
costs = list(map(int, input().split(' ')))
(cost, costF) = (0, 0)
(string, stringF) = ('', '')
for i in range(n):
	s = input()
	sF = s[::-1]
	if s >= string and s >= stringF:
		newCost = min(cost, costF)
	elif s >= string:
		newCost = cost
	elif s >= stringF:
		newCost = costF
	else:
		newCost = 10 ** 16
	if sF >= string and sF >= stringF:
		newCostF = min(cost, costF) + costs[i]
	elif sF >= string:
		newCostF = cost + costs[i]
	elif sF >= stringF:
		newCostF = costF + costs[i]
	else:
		newCostF = 10 ** 16
	string = s
	stringF = sF
	cost = newCost
	costF = newCostF
if cost > 10 ** 16 - 1 and costF > 10 ** 16 - 1:
	print(-1)
else:
	print(min(cost, costF))


(n, l) = (int(input()), [(0, '')])
for i in map(int, input().split()):
	s = input()
	l = sorted(((x + y, b) for (y, b) in ((0, s), (i, s[::-1])) for (x, a) in l if a <= b))
	for i in range(len(l) - 1, 0, -1):
		for j in range(i):
			if l[i][1] >= l[j][1]:
				del l[i]
				break
print(min(l)[0] if l else -1)


from sys import stdin, exit
input = stdin.readline
n = int(input())
cost = list(map(int, input().split()))
arr = [input().rstrip('\n') for i in range(n)]
rarr = [i[::-1] for i in arr]
dp = [[float('inf') for i in range(n + 2)] for j in range(2)]
dp[0][0] = 0
dp[1][0] = cost[0]
for i in range(1, n):
	if arr[i] >= arr[i - 1]:
		dp[0][i] = min(dp[0][i], dp[0][i - 1])
	if arr[i] >= rarr[i - 1]:
		dp[0][i] = min(dp[0][i], dp[1][i - 1])
	if rarr[i] >= arr[i - 1]:
		dp[1][i] = min(dp[1][i], dp[0][i - 1] + cost[i])
	if rarr[i] >= rarr[i - 1]:
		dp[1][i] = min(dp[1][i], dp[1][i - 1] + cost[i])
if min(dp[0][n - 1], dp[1][n - 1]) == float('inf'):
	print(-1)
else:
	print(min(dp[0][n - 1], dp[1][n - 1]))


n = int(input())
a = list(map(int, input().split()))
s = []
r = []
d = [0] * (n + 1)
MAX = int(1e+18)
for i in range(0, n + 1):
	d[i] = [0] * 2
for i in range(0, n):
	s.append(input())
	r.append(s[i][::-1])
d[0][0] = 0
d[0][1] = a[0]
for i in range(1, n):
	for j in range(0, 2):
		if j == 0:
			st = s[i]
		else:
			st = r[i]
		if j == 1:
			d[i][j] = a[i]
		if st >= s[i - 1] and st >= r[i - 1]:
			d[i][j] += min(d[i - 1][0], d[i - 1][1])
		elif st >= s[i - 1]:
			d[i][j] += d[i - 1][0]
		elif st >= r[i - 1]:
			d[i][j] += d[i - 1][1]
		else:
			d[i][j] = MAX
		d[i][j] = min(d[i][j], MAX)
print(-1 if d[n - 1][0] == MAX and d[n - 1][1] == MAX else min(d[n - 1][0], d[n - 1][1]))


n = int(input())
cost = list(map(int, input().strip().split()))
w = []
for i in range(n):
	w.append(input())
dp = [[float('inf'), float('inf')] for i in range(n)]
dp[0] = [0, cost[0]]
for i in range(1, n):
	p = w[i - 1]
	s = w[i]
	r = ''.join((i for i in [s[i] for i in range(len(s) - 1, -1, -1)]))
	rP = ''.join((i for i in [p[i] for i in range(len(p) - 1, -1, -1)]))
	if r >= w[i - 1]:
		dp[i][1] = cost[i] + dp[i - 1][0]
	if r >= rP:
		dp[i][1] = min(dp[i][1], cost[i] + dp[i - 1][1])
	if s >= p:
		dp[i][0] = dp[i - 1][0]
	if s >= rP:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
ans = min(dp[-1])
if ans == float('inf'):
	print(-1)
else:
	print(ans)


n = int(input())
c = input().split(' ')
for i in range(n):
	c[i] = int(c[i])
norm = ['' for i in range(n)]
rev = ['' for i in range(n)]
for i in range(n):
	norm[i] = input()
	rev[i] = norm[i][::-1]
MAX = 1e+18
dp = [[MAX for i in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	if norm[i] >= rev[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if norm[i] >= norm[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if rev[i] >= rev[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	if rev[i] >= norm[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
ans = min(dp[n - 1][0], dp[n - 1][1])
if ans == MAX:
	print(-1)
else:
	print(ans)


n = int(input())
s = list(map(int, input().split()))
q = [input() for i in range(n)]
q1 = [q[i][::-1] for i in range(n)]
maxx = 10 ** 14
dp = [[maxx, maxx] for i in range(n)]
dp[0][0] = 0
dp[0][1] = s[0]
for i in range(1, n):
	if q1[i] >= q[i - 1]:
		dp[i][1] = dp[i - 1][0] + s[i]
	if q1[i] >= q1[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + s[i])
	if q[i] >= q1[i - 1]:
		dp[i][0] = dp[i - 1][1]
	if q[i] >= q[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
ans = min(dp[-1])
if ans >= maxx:
	print(-1)
else:
	print(ans)


n = int(input())
c = list(map(int, input().split(' ')))
nodes = dict()
nodes[''] = 0
depth = 0
while depth < n:
	new_nodes = dict()
	s = input()
	for node in nodes.keys():
		if s >= node:
			if s in new_nodes:
				new_nodes[s] = min(new_nodes[s], nodes[node])
			else:
				new_nodes[s] = nodes[node]
		if s[::-1] >= node:
			if s[::-1] in new_nodes:
				new_nodes[s[::-1]] = min(new_nodes[s[::-1]], nodes[node] + c[depth])
			else:
				new_nodes[s[::-1]] = nodes[node] + c[depth]
	nodes = new_nodes
	depth += 1
if len(nodes) > 0:
	print(min(nodes.values()))
else:
	print(-1)


from sys import stdin, stdout
for _ in range(1):
	n = int(stdin.readline())
	cost = list(map(int, stdin.readline().split()))
	s = []
	for _ in range(n):
		s += [input()]
	(rev, dont) = (cost[0], 0)
	for i in range(1, n):
		prev = s[i - 1]
		rev_of_prev = s[i - 1][::-1]
		d = r = float('inf')
		rev_of_cur = s[i][::-1]
		if s[i] >= prev:
			d = dont
		if s[i] >= rev_of_prev:
			d = min(d, rev)
		if rev_of_cur >= prev:
			r = cost[i] + dont
		if rev_of_cur >= rev_of_prev:
			r = min(r, cost[i] + rev)
		(rev, dont) = (r, d)
	ans = min(rev, dont)
	print(ans if ans != float('inf') else -1)


def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())
n = ii()
c = li()
st = []
for i in range(n):
	s = si()
	st.append(s)
dp = [[0 for j in range(2)] for i in range(n)]
fin = 0
dp[0][1] = c[0]
for i in range(1, n):
	(flag1, flag2) = (0, 0)
	l2 = []
	if st[i] >= st[i - 1]:
		if dp[i - 1][0] != -1:
			l2.append(dp[i - 1][0])
			flag1 = 1
	if st[i] >= st[i - 1][::-1]:
		if dp[i - 1][1] != -1:
			l2.append(dp[i - 1][1])
			flag1 = 1
	l1 = []
	if st[i][::-1] >= st[i - 1]:
		if dp[i - 1][0] != -1:
			l1.append(dp[i - 1][0] + c[i])
			flag2 = 1
	if st[i][::-1] >= st[i - 1][::-1]:
		if dp[i - 1][1] != -1:
			l1.append(dp[i - 1][1] + c[i])
			flag2 = 1
	if flag1 == 0 and flag2 == 0:
		fin = 1
		print(-1)
		break
	else:
		if flag1 == 1:
			dp[i][0] = min(l2)
		if flag1 == 0:
			dp[i][0] = -1
		if flag2 == 1:
			dp[i][1] = min(l1)
		if flag2 == 0:
			dp[i][1] = -1
if fin == 0:
	if dp[n - 1][0] == -1:
		print(dp[n - 1][1])
	elif dp[n - 1][1] == -1:
		print(dp[n - 1][0])
	else:
		print(min(dp[n - 1][0], dp[n - 1][1]))


import math
n = int(input())
a = list(map(int, input().split()))
s = [input() for _ in range(n)]
dp = [[0] * 2 for _ in range(n)]
dp[0] = [0, a[0]]
for i in range(1, n):
	dp[i] = [math.inf] * 2
	if s[i - 1] <= s[i]:
		dp[i][0] = min(dp[i - 1][0], dp[i][0])
	if s[i - 1][::-1] <= s[i]:
		dp[i][0] = min(dp[i - 1][1], dp[i][0])
	if s[i - 1] <= s[i][::-1]:
		dp[i][1] = min(dp[i - 1][0] + a[i], dp[i][1])
	if s[i - 1][::-1] <= s[i][::-1]:
		dp[i][1] = min(dp[i - 1][1] + a[i], dp[i][1])
res = min(dp[-1])
print(-1 if res == math.inf else res)


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInt():
	return int(sys.stdin.readline().rstrip())

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def printOutput(ans):
	if ans == math.inf:
		sys.stdout.write(str(-1) + '\n')
	else:
		sys.stdout.write(str(ans) + '\n')

def itdfs(strings):
	stack = [0]
	visited = {}
	end = len(strings) - 1
	while stack:
		nxt = stack.pop()
	return

def solve(strNum, strings, costs):
	tab = [[math.inf for _ in range(2)] for _ in range(strNum)]
	prevString = strings[0]
	prevRev = ''.join([i for i in reversed(prevString)])
	tab[0][0] = 0
	tab[0][1] = costs[0]
	for i in range(1, strNum):
		curString = strings[i]
		curRev = ''.join([i for i in reversed(curString)])
		if curString >= prevString:
			tab[i][0] = tab[i - 1][0]
		if curString >= prevRev:
			tab[i][0] = min(tab[i][0], tab[i - 1][1])
		if curRev >= prevString:
			tab[i][1] = tab[i - 1][0] + costs[i]
		if curRev >= prevRev:
			tab[i][1] = min(tab[i][1], tab[i - 1][1] + costs[i])
		prevString = curString
		prevRev = curRev
	return min(tab[-1])

def readinput():
	strNum = getInt()
	costs = list(getInts())
	strings = []
	for _ in range(strNum):
		strings.append(getString())
	printOutput(solve(strNum, strings, costs))
readinput()


n = int(input())
c = list(map(int, input().split()))
dp = [[0 for i in range(2)] for j in range(n)]
x = input()
y = x[::-1]
dp[0][1] = c[0]
for i in range(1, n):
	dp[i] = [float('inf'), float('inf')]
	a = input()
	b = a[::-1]
	if a >= x:
		dp[i][0] = dp[i - 1][0]
	if a >= y:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if b >= x:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
	if b >= y:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	(x, y) = (a, b)
minm = min(dp[n - 1])
if minm == float('inf'):
	print(-1)
else:
	print(minm)


n = int(input())
arr = list(map(int, input().split()))
li = []
cost = []
for i in range(n):
	s = input()
	x = s[::-1]
	li.append([s, x])
	cost.append([0, arr[i]])
md = 10 ** 16
flag = 0
for i in range(1, n):
	if li[i][0] >= li[i - 1][0]:
		x = cost[i - 1][0]
	else:
		x = md
	if li[i][0] >= li[i - 1][1]:
		y = cost[i - 1][1]
	else:
		y = md
	if li[i][1] >= li[i - 1][0]:
		m = cost[i - 1][0]
	else:
		m = md
	if li[i][1] >= li[i - 1][1]:
		k = cost[i - 1][1]
	else:
		k = md
	if min(x, y) == md and min(m, k) == md:
		flag = 1
		break
	cost[i][0] += min(x, y)
	cost[i][1] += min(m, k)
if flag:
	print(-1)
else:
	print(min(cost[n - 1]))


n = int(input())
a = list(map(int, input().split()))
p1 = input()
p2 = p1[::-1]
(cnt1, cnt2) = (0, a[0])
b = 0
for i in range(1, n):
	p3 = input()
	p4 = p3[::-1]
	if p1 > p3 and p2 > p3 and (p1 > p4) and (p2 > p4):
		b = 1
	(cnt3, cnt4) = (-1, -1)
	c = 0
	if p1 <= p3 or p2 <= p3:
		if p1 <= p3:
			cnt3 = cnt1
		if p2 <= p3 and (cnt2 <= cnt3 or cnt3 == -1):
			cnt3 = cnt2
	else:
		c = 1
	if p1 <= p4 or p2 <= p4:
		if p1 <= p4:
			cnt4 = cnt1
		if p2 <= p4 and (cnt2 <= cnt4 or cnt4 == -1):
			cnt4 = cnt2
		cnt4 += a[i]
		if c:
			p3 = p4
			cnt3 = cnt4
	else:
		p4 = p3
		cnt4 = cnt3
	(cnt1, p1) = (cnt3, p3)
	(cnt2, p2) = (cnt4, p4)
if b:
	print(-1)
else:
	print(min(cnt3, cnt4))


def main():
	(n, l) = (int(input()), [(0, '')])
	for c in map(int, input().split()):
		s = input()
		l = [(x + dx, b) for (dx, b) in ((0, s), (c, s[::-1])) for (x, a) in l if a <= b]
		l.sort()
		for i in range(len(l) - 1, 0, -1):
			for j in range(i):
				if l[i][1] >= l[j][1]:
					del l[i]
					break
	print(min(l)[0] if l else -1)
main()


INF = 10 ** 18

def read():
	return [int(x) for x in input().split()]

def main():
	(n,) = read()
	c = read()
	a = []
	b = []
	for i in range(0, n):
		s = input()
		a.append(s)
		b.append(s[::-1])
	dp = [[0, 0] for _ in range(0, n)]
	dp[0][0] = 0
	dp[0][1] = c[0]
	for i in range(1, n):
		dp[i][0] = INF
		dp[i][1] = INF
		if a[i] >= a[i - 1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if a[i] >= b[i - 1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if b[i] >= a[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
		if b[i] >= b[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	res = min(dp[n - 1][0], dp[n - 1][1])
	print(res == INF and -1 or res)
main()


inf = 10 ** 100
n = int(input())
cost = list(map(int, input().split()))
s = []
for i in range(n):
	u = input()
	s.append(u)
r = [i[::-1] for i in s]
dp = [[inf, inf] for j in range(n)]
dp[0] = [0, cost[0]]
for i in range(1, n):
	if s[i] >= s[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if s[i] >= r[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if r[i] >= s[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + cost[i])
	if r[i] >= r[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i])
if min(dp[-1]) == inf:
	print(-1)
else:
	print(min(dp[-1]))


n = int(input())
costs = list(map(int, input().split()))
strings = []
for i in range(n):
	strings.append(input())
cost_tuples = [(0, costs[0])]
for i in range(1, n):
	(a1, a2) = (-1, -1)
	if cost_tuples[i - 1][0] >= 0 and strings[i] >= strings[i - 1]:
		a1 = cost_tuples[i - 1][0]
	if cost_tuples[i - 1][0] >= 0 and ''.join(reversed(strings[i])) >= strings[i - 1]:
		a2 = cost_tuples[i - 1][0] + costs[i]
	if cost_tuples[i - 1][1] >= 0 and strings[i] >= ''.join(reversed(strings[i - 1])):
		a1 = cost_tuples[i - 1][1] if a1 == -1 or (a1 != -1 and cost_tuples[i - 1][1] < a1) else a1
	if cost_tuples[i - 1][1] >= 0 and ''.join(reversed(strings[i])) >= ''.join(reversed(strings[i - 1])):
		a2 = cost_tuples[i - 1][1] + costs[i] if a2 == -1 or (a2 != -1 and cost_tuples[i - 1][1] + costs[i] < a2) else a2
	cost_tuples.append((a1, a2))
	if a1 == -1 and a2 == -1:
		break
if cost_tuples[-1][0] == -1 and cost_tuples[-1][1] == -1:
	print(-1)
elif cost_tuples[-1][0] == -1:
	print(cost_tuples[-1][1])
elif cost_tuples[-1][1] == -1:
	print(cost_tuples[-1][0])
else:
	print(min(cost_tuples[-1]))


import sys

def rec(N, C, S, pos, prev, dp):
	if (pos, prev) in dp:
		return dp[pos, prev]
	if pos >= N:
		return 0
	sr = S[pos][::-1]
	if pos == 0:
		sp = ''
	elif prev == False:
		sp = S[pos - 1]
	else:
		sp = S[pos - 1][::-1]
	print('sr=', sr, 'sp=', sp, 'S[pos]=', S[pos], 'sr<S[pos]=', sr < S[pos], 'C[pos]=', C[pos])
	bestSum = 10 ** 18
	sumCurrWFlip = 10 ** 18
	sumCurrWOFlip = 10 ** 18
	if sr < S[pos] and sr >= sp:
		sumBelowWithFlip = rec(N, C, S, pos + 1, True, dp)
		sumCurrWFlip = sumBelowWithFlip + C[pos]
		print('pos=', pos, 'sumCurrWFlip=', sumCurrWFlip)
	if S[pos] >= sp:
		sumBelowWithoutFlip = rec(N, C, S, pos + 1, False, dp)
		sumCurrWOFlip = sumBelowWithoutFlip
		print('pos=', pos, 'sumCurrWOFlip=', sumCurrWOFlip)
	if sumCurrWFlip < sumCurrWOFlip:
		bestSum = sumCurrWFlip
		dp[pos, True] = bestSum
	else:
		bestSum = sumCurrWOFlip
		dp[pos, False] = bestSum
	return bestSum

def answer(n, c, s):
	dp = dict()
	pos = 0
	prev = False
	ans = rec(n, c, s, pos, prev, dp)
	print('dp=', dp)
	if ans == 10 ** 18:
		return -1
	return ans

def answer2(n, C, S):
	dp = [[10 ** 18 for j in range(2)] for i in range(n + 1)]
	dp[0][0] = 0
	dp[0][1] = 0
	for i in range(1, n + 1):
		sc = S[i - 1]
		scr = sc[::-1]
		if i - 2 >= 0:
			sp = S[i - 2]
		else:
			sp = ''
		spr = sp[::-1]
		if sc >= sp:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if sc >= spr:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if scr >= sp:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + C[i - 1])
		if scr >= spr:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + C[i - 1])
	ans = min(dp[n][0], dp[n][1])
	if ans == 10 ** 18:
		return -1
	return ans

def main():
	n = int(sys.stdin.readline())
	c = tuple(map(int, sys.stdin.readline().split()))
	s = [None for i in range(n)]
	for i in range(n):
		s[i] = sys.stdin.readline().rstrip()
	print(answer2(n, c, s))
	return
main()


n = int(input())
cost = list(map(int, input().split()))
a = []
for i in range(n):
	a.append(input())
dp = [[0 for i in range(n)] for j in range(2)]
isValid = True
dp[0][0] = cost[0]
maxValue = float('inf')
for i in range(1, n):
	ans = maxValue
	if a[i - 1] <= a[i] and dp[1][i - 1] != -1:
		ans = min(ans, dp[1][i - 1])
	if a[i - 1][::-1] <= a[i] and dp[0][i - 1] != -1:
		ans = min(ans, dp[0][i - 1])
	if ans == maxValue:
		dp[1][i] = -1
	else:
		dp[1][i] = ans
	ans = maxValue
	if a[i - 1] <= a[i][::-1] and dp[1][i - 1] != -1:
		ans = min(ans, dp[1][i - 1] + cost[i])
	if a[i - 1][::-1] <= a[i][::-1] and dp[0][i - 1] != -1:
		ans = min(ans, dp[0][i - 1] + cost[i])
	if ans == maxValue:
		dp[0][i] = -1
	else:
		dp[0][i] = ans
	if dp[0][i] == dp[1][i] and dp[0][i] == -1:
		isValid = False
		break
if isValid:
	if dp[1][n - 1] == -1:
		print(dp[0][n - 1])
	elif dp[0][n - 1] == -1:
		print(dp[1][n - 1])
	else:
		print(min(dp[1][n - 1], dp[0][n - 1]))
else:
	print(-1)


lines = int(input())
energy = input().split()
energies = []
prevMins = [0, int(energy[0])]
prevS = ['', '']
prevS[0] = input()
prevS[1] = prevS[0][::-1]
curS = ['', '']
curMins = [0, 0]
fail = False
for i in range(1, lines):
	energy[i] = int(energy[i])
	curS[0] = input()
	curS[1] = curS[0][::-1]
	curMins[0] = -1
	curMins[1] = -1
	if prevMins[0] >= 0:
		if curS[0] >= prevS[0]:
			curMins[0] = prevMins[0]
		if curS[1] >= prevS[0]:
			curMins[1] = prevMins[0] + energy[i]
	if prevMins[1] >= 0:
		if curS[0] >= prevS[1]:
			if curMins[0] == -1:
				curMins[0] = prevMins[1]
			else:
				curMins[0] = min(curMins[0], prevMins[1])
		if curS[1] >= prevS[1]:
			if curMins[1] == -1:
				curMins[1] = prevMins[1] + energy[i]
			else:
				curMins[1] = min(curMins[1], prevMins[1] + energy[i])
	if curMins[0] < 0 and curMins[1] < 0:
		fail = True
		break
	else:
		prevMins[0] = curMins[0]
		prevMins[1] = curMins[1]
		prevS[0] = curS[0]
		prevS[1] = curS[1]
if fail:
	print(-1)
elif prevMins[0] == -1:
	print(prevMins[1])
elif prevMins[1] == -1:
	print(prevMins[0])
else:
	print(min(prevMins[0], prevMins[1]))


n = int(input())
p = list(map(int, input().split()))
dp = [[float('inf'), float('inf')] for _ in range(n)]
(dp[0][0], dp[0][1]) = (0, p[0])
last = input()
for i in range(1, n):
	cur = input()
	if cur >= last:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if cur >= last[::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if cur[::-1] >= last:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + p[i])
	if cur[::-1] >= last[::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + p[i])
	last = cur
ans = min(dp[n - 1][0], dp[n - 1][1])
if ans == float('inf'):
	ans = -1
print(ans)


n = int(input())
cs = [int(c) for c in input().split()]
words = [input() for _ in range(n)]
backwords = [w[::-1] for w in words]
table = [[0, cs[0]] if i == 0 else [float('inf')] * 2 for i in range(n)]
for i in range(1, n):
	if table[i - 1][0] is not None:
		if words[i] >= words[i - 1]:
			table[i][0] = min(table[i][0], table[i - 1][0])
		if backwords[i] >= words[i - 1]:
			table[i][1] = min(table[i][1], table[i - 1][0] + cs[i])
	if table[i - 1][1] is not None:
		if words[i] >= backwords[i - 1]:
			table[i][0] = min(table[i][0], table[i - 1][1])
		if backwords[i] >= backwords[i - 1]:
			table[i][1] = min(table[i][1], table[i - 1][1] + cs[i])
	if table[i][0] == table[i][1] == float('inf'):
		print(-1)
		exit()
print(min(table[-1]))


def isGreaterThan(string1, string2):
	minLength = min(len(string1), len(string2))
	i = 0
	while i < minLength and string1[i] == string2[i]:
		i += 1
	if i == minLength:
		if len(string2) == minLength:
			return True
	elif string1[i] > string2[i]:
		return True
	return False
MAX_INT = 10000000000000000
n = int(input())
c = list(map(int, input().split()))
strings = []
for _ in range(n):
	strings += [input()]
dp = [[MAX_INT, MAX_INT] for i in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	string1 = strings[i - 1]
	string2 = strings[i]
	if isGreaterThan(string2, string1):
		if isGreaterThan(string2, string1[::-1]):
			dp[i][0] = min(dp[i - 1])
		else:
			dp[i][0] = dp[i - 1][0]
	elif isGreaterThan(string2, string1[::-1]):
		dp[i][0] = dp[i - 1][1]
	string2 = string2[::-1]
	if isGreaterThan(string2, string1):
		if isGreaterThan(string2, string1[::-1]):
			dp[i][1] = min(dp[i - 1]) + c[i]
		else:
			dp[i][1] = dp[i - 1][0] + c[i]
	elif isGreaterThan(string2, string1[::-1]):
		dp[i][1] = dp[i - 1][1] + c[i]
if min(dp[n - 1]) == MAX_INT:
	print(-1)
else:
	print(min(dp[n - 1]))


n = int(input())
c = list(map(int, input().split()))
l = r = ''
a = b = 0
for _ in range(n):
	x = y = float('inf')
	i = input()
	rev = i[::-1]
	if i >= l:
		x = a
	if i >= r:
		x = min(x, b)
	if rev >= l:
		y = a + c[_]
	if rev >= r:
		y = min(y, b + c[_])
	a = x
	b = y
	l = i
	r = rev
res = min(a, b)
if res == float('inf'):
	print(-1)
else:
	print(res)


inf = float('inf')
n = int(input())
costs = [int(i) for i in input().split()]
done = False
words = []
rwords = []
for i in range(n):
	s = input()
	if i >= 1:
		if words[i - 1] > s and rwords[i - 1] > s:
			if words[i - 1] > s[::-1] and rwords[i - 1] > s[::-1]:
				print(-1)
				done = True
				break
	words.append(s)
	rwords.append(s[::-1])
if not done:
	prev = [0, 0]
	if not words[0] == rwords[0]:
		prev[1] = costs[0]
	for i in range(1, n):
		curr = [inf, inf]
		if words[i - 1] <= words[i] and rwords[i - 1] <= words[i]:
			curr[0] = min(prev[0], prev[1])
		elif words[i - 1] <= words[i]:
			curr[0] = prev[0]
		elif rwords[i - 1] <= words[i]:
			curr[0] = prev[1]
		if words[i] == rwords[i]:
			cost = 0
		else:
			cost = costs[i]
		if words[i - 1] <= rwords[i] and rwords[i - 1] <= rwords[i]:
			curr[1] = min(prev[0], prev[1]) + cost
		elif words[i - 1] <= rwords[i]:
			curr[1] = prev[0] + cost
		elif rwords[i - 1] <= rwords[i]:
			curr[1] = prev[1] + cost
		prev = curr
	if min(prev) == inf:
		print(-1)
	else:
		print(min(prev))


import sys
line = sys.stdin.readlines()
n = int(line[0])
c = list(map(int, line[1].split()))
INF = 1e+16
(p, pr) = ('', '')
(c0, cr) = (0, 0)
for i in range(n):
	s = line[i + 2].rstrip('\r\n')
	sr = s[::-1]
	c00 = c0 if p <= s else INF
	cr0 = cr if pr <= s else INF
	c0r = c0 + c[i] if p <= sr else INF
	crr = cr + c[i] if pr <= sr else INF
	(p, pr) = (s, sr)
	(c0, cr) = (min(c00, cr0), min(c0r, crr))
ans = min(c0, cr)
if ans >= INF:
	print(-1)
else:
	print(ans)


n = int(input())
c = list(map(int, input().split()))
s = []
for i in range(n):
	st = input()
	s.append((st, st[::-1]))
dp = [[float('inf')] * 2 for i in range(n)]
dp[0] = [0, c[0]]
for i in range(1, n):
	for j in range(2):
		for k in range(2):
			if s[i - 1][j] <= s[i][k]:
				dp[i][k] = min(dp[i][k], dp[i - 1][j] + c[i] * k)
if min(dp[-1]) == float('inf'):
	print(-1)
else:
	print(min(dp[-1]))


from sys import stdin

def main():
	(n, l) = (int(input()), [(0, '')])
	for (c, s) in zip(map(int, input().split()), stdin.read().splitlines()):
		l = sorted(((x + y, b) for (y, b) in ((0, s), (c, s[::-1])) for (x, a) in l if a <= b))
		for i in range(len(l) - 1, 0, -1):
			for j in range(i):
				if l[i][1] >= l[j][1]:
					del l[i]
					break
	print(min(l)[0] if l else -1)
main()


n = int(input())
arr = list(map(int, input().split()))
t = ''
a = 0
b = 0
for i in range(n):
	c = input()
	x = y = 10 ** 15
	if c >= t:
		x = a
	if c >= t[::-1]:
		x = min(x, b)
	if c[::-1] >= t:
		y = a + arr[i]
	if c[::-1] >= t[::-1]:
		y = min(y, b + arr[i])
	a = x
	b = y
	t = c
ans = min(a, b)
if ans >= 10 ** 15:
	print(-1)
else:
	print(ans)


import sys
n = int(sys.stdin.readline().strip())
c = list(map(int, sys.stdin.readline().strip().split()))
w = [sys.stdin.readline().strip() for _ in range(n)]

def solve(n, c, w):
	_MAX_VAL = 10 ** 6 * 10 ** 9
	t1 = [0] + [_MAX_VAL] * (n - 1)
	t2 = [c[0]] + [_MAX_VAL] * (n - 1)
	w1 = w
	w2 = [_[::-1] for _ in w]
	for i in range(1, n):
		if w1[i] >= w1[i - 1]:
			t1[i] = min(t1[i], t1[i - 1])
		if w1[i] >= w2[i - 1]:
			t1[i] = min(t1[i], t2[i - 1])
		if w2[i] >= w1[i - 1]:
			t2[i] = min(t2[i], t1[i - 1] + c[i])
		if w2[i] >= w2[i - 1]:
			t2[i] = min(t2[i], t2[i - 1] + c[i])
		if t1[i] == _MAX_VAL and t2[i] == _MAX_VAL:
			return -1
	return min(t1[n - 1], t2[n - 1])
print(solve(n, c, w))


n = int(input())
N = [0] + list(map(int, input().split()))
S = [[''] * 2 for i in range(n + 1)]
for i in range(1, n + 1):
	s = input()
	S[i] = [s, s[::-1]]
INF = 10 ** 15
F1 = [[INF] * 2 for i in range(n + 1)]
F2 = [[INF] * 2 for i in range(n + 1)]
F1[1][0] = 0
F1[1][1] = N[1]
F2[1][0] = 0
F2[1][1] = N[1]
for i in range(2, n + 1):
	if S[i][0] >= S[i - 1][0]:
		F1[i][0] = min(F1[i - 1][0], F2[i - 1][0])
	if S[i][0] >= S[i - 1][1]:
		F2[i][0] = min(F1[i - 1][1], F2[i - 1][1])
	if S[i][1] >= S[i - 1][0]:
		F1[i][1] = min(F1[i - 1][0], F2[i - 1][0]) + N[i]
	if S[i][1] >= S[i - 1][1]:
		F2[i][1] = min(F1[i - 1][1], F2[i - 1][1]) + N[i]
if min(F1[n][0], F1[n][1], F2[n][0], F2[n][1]) == INF:
	print(-1)
else:
	print(min(F1[n][0], F1[n][1], F2[n][0], F2[n][1]))


def judge(word):
	if word == word[::-1]:
		return 'same'
	elif word < word[::-1]:
		return 'big'
	else:
		return 'small'

def proc(words, costs):
	word = words[0]
	cost = costs[0]
	idx = 0
	(saved_small_word, saved_big_word) = (word, word[::-1]) if word <= word[::-1] else (word[::-1], word)
	j = judge(word)
	if j == 'same' or j == 'big':
		res = [0, 0]
		yield res
	else:
		res = [cost, 0]
		yield res
	while idx < len(costs) - 1:
		idx = idx + 1
		word = words[idx]
		cost = costs[idx]
		j = judge(word)
		if word < saved_small_word and word[::-1] < saved_small_word:
			yield (-1, -1)
		elif j == 'same':
			if word < saved_big_word:
				(saved_small_word, saved_big_word) = (word, word)
				res[1] = res[0]
				yield res
			else:
				(saved_small_word, saved_big_word) = (word, word)
				res[0] = res[1]
				yield res
		elif j == 'big':
			if saved_small_word <= word:
				if saved_big_word <= word:
					(saved_small_word, saved_big_word) = (word, word)
					res[0] = res[1]
					yield res
				elif word[::-1] < saved_big_word:
					(saved_small_word, saved_big_word) = (word, word)
					res[1] = res[0]
					yield res
				elif res[0] <= res[1] + cost:
					(saved_small_word, saved_big_word) = (word, word)
					res[1] = res[0]
					yield res
				else:
					(saved_small_word, saved_big_word) = (word, word[::-1])
					res[1] += cost
					yield res
			elif word[::-1] < saved_big_word:
				(saved_small_word, saved_big_word) = (word[::-1], word[::-1])
				(res[0], res[1]) = (res[0] + cost, res[0] + cost)
				yield res
			else:
				(saved_small_word, saved_big_word) = (word[::-1], word[::-1])
				(res[0], res[1]) = (res[1] + cost, res[1] + cost)
				yield res
		elif word < saved_big_word:
			if word[::-1] < saved_small_word:
				(saved_small_word, saved_big_word) = (word, word)
				res[1] = res[0]
				yield res
			else:
				(saved_small_word, saved_big_word) = (word[::-1], word)
				(res[0], res[1]) = (res[0] + cost, res[0])
				yield res
		elif word[::-1] < saved_small_word:
			(saved_small_word, saved_big_word) = (word, word)
			res[0] = word[1]
			yield res
		elif word[::-1] < saved_big_word:
			(saved_small_word, saved_big_word) = (word[::-1], word)
			(res[0], res[1]) = (res[0] + cost, res[1])
			yield res
		else:
			(saved_small_word, saved_big_word) = (word[::-1], word)
			(res[0], res[1]) = (res[1] + cost, res[1])
			yield res
cnt = int(input())
costs = list(map(int, input().strip().split()))
words = []
for i in range(cnt):
	words.append(input().strip())
for i in proc(words, costs):
	res = i
	if res[0] == -1:
		break
print(res[-1])


n = int(input())
l = list(map(int, input().split()))
dp = [[float('inf'), float('inf')] for i in range(n)]
k = input()
dp[0][0] = 0
dp[0][1] = l[0]
for i in range(1, n):
	h = input()
	flag = 0
	if h >= k:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
		flag = 1
	if h[::-1] >= k:
		dp[i][1] = min(dp[i][1], dp[i - 1][0]) + l[i]
		flag = 1
	if h >= k[::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
		flag = 1
	if h[::-1] >= k[::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + l[i])
		flag = 1
	if flag == 0:
		print(-1)
		exit()
	k = h
u = min(dp[n - 1][0], dp[n - 1][1])
if u == float('inf'):
	print(-1)
	exit()
print(u)


import math
import sys
from bisect import bisect_right, bisect_left, insort_right
from collections import Counter, defaultdict
from heapq import heappop, heappush
from itertools import accumulate
from sys import stdout
R = lambda : map(int, input().split())
n = int(input())
arr = list(R())
ss = [input() for _ in range(n)] + ['']
dp = [[0, 0] for i in range(n + 1)]
for i in range(n):
	dp[i][0] = min(dp[i - 1][0] if ss[i] >= ss[i - 1] else math.inf, dp[i - 1][1] if ss[i] >= ss[i - 1][::-1] else math.inf)
	dp[i][1] = arr[i] + min(dp[i - 1][0] if ss[i][::-1] >= ss[i - 1] else math.inf, dp[i - 1][1] if ss[i][::-1] >= ss[i - 1][::-1] else math.inf)
print(min(dp[n - 1]) if min(dp[n - 1]) < math.inf else -1)


n = int(input())
z = 10 ** 9 * n + 1
c = list(map(int, input().split()))
s = [input() for i in range(n)]
mat = [[z, z] for i in range(n)]
mat[0][0] = 0
mat[0][1] = c[0]
for i in range(1, n):
	s2 = s[i][::-1]
	s1 = s[i - 1][::-1]
	(a, b, p, q) = (z, z, z, z)
	if s[i] >= s[i - 1]:
		a = mat[i - 1][0]
	if s[i] >= s1:
		b = mat[i - 1][1]
	mat[i][0] = min(a, b)
	if s2 >= s[i - 1]:
		p = mat[i - 1][0]
	if s2 >= s1:
		q = mat[i - 1][1]
	mat[i][1] = c[i] + min(p, q)
res = min(mat[n - 1][0], mat[n - 1][1])
if res >= z:
	print(-1)
else:
	print(res)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1
for _ in range(t):
	n = ii()
	c = li()
	dp = [[10000000000000000000, 10000000000000000000] for i in range(n + 1)]
	st = []
	strev = []
	for i in range(n):
		s = si()
		sr = s[::-1]
		st.append(s)
		strev.append(sr)
		if i == 0:
			dp[0][0] = 0
			dp[0][1] = c[0]
			continue
		if s >= st[-2]:
			dp[i][0] = dp[i - 1][0]
		if s >= strev[-2]:
			dp[i][0] = min(dp[i - 1][1], dp[i][0])
		if sr >= st[-2]:
			dp[i][1] = dp[i - 1][0] + c[i]
		if sr >= strev[-2]:
			dp[i][1] = min(dp[i - 1][1] + c[i], dp[i][1])
	ans = min(dp[n - 1][0], dp[n - 1][1])
	if ans == 10000000000000000000:
		ans = -1
	print(ans)


n = int(input())
g = list(map(int, input().split()))

def rv(s):
	return s[::-1]
ss = input()
rss = rv(ss)
(d, p) = (0, g[0])
for i in range(1, n):
	s = input()
	rs = rv(s)
	(x, y) = (10 ** 16, 10 ** 16)
	if s >= ss:
		x = d
	if s >= rss:
		x = min(x, p)
	if rs >= ss:
		y = d + g[i]
	if rs >= rss:
		y = min(y, p + g[i])
	d = x
	p = y
	ss = s
	rss = rs
jj = min(d, p)
if jj == 10 ** 16:
	print(-1)
else:
	print(jj)


from sys import stdin
N = int(stdin.readline().rstrip())
energies = [int(x) for x in stdin.readline().rstrip().split()]
dp = [-1] * (N + 1)
dp_reverse = [-1] * (N + 1)
dp[0] = 0
dp_reverse[0] = 0
last_word = ''
last_word_reverse = ''
for n in range(1, N + 1):
	word = stdin.readline().rstrip()
	word_reverse = word[::-1]
	if dp[n - 1] != -1:
		if last_word <= word:
			dp[n] = dp[n - 1]
		if last_word <= word_reverse:
			dp_reverse[n] = dp[n - 1] + energies[n - 1]
	if dp_reverse[n - 1] != -1:
		if last_word_reverse <= word and (dp[n] == -1 or dp_reverse[n - 1] < dp[n]):
			dp[n] = dp_reverse[n - 1]
		if last_word_reverse <= word_reverse and (dp_reverse[n] == -1 or dp_reverse[n - 1] + energies[n - 1] < dp_reverse[n]):
			dp_reverse[n] = dp_reverse[n - 1] + energies[n - 1]
	last_word = word
	last_word_reverse = word_reverse
if dp[N] == -1 and dp_reverse[N] == -1:
	print(-1)
elif dp[N] == -1:
	print(dp_reverse[N])
elif dp_reverse[N] == -1:
	print(dp[N])
else:
	print(min(dp[N], dp_reverse[N]))


inf = 10 ** 100
n = int(input())
c = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(input())
re = [i[::-1] for i in t]
dp = [[inf, inf] for i in range(n)]
dp[0] = [0, c[0]]
for i in range(1, n):
	if t[i] >= t[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if t[i] >= re[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if re[i] >= t[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
	if re[i] >= re[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
if min(dp[-1]) == inf:
	print(-1)
else:
	print(min(dp[-1]))


def solution(c):
	max_s = 2 * sum(c) + 1
	ans_rotated = c[0]
	ans_still = 0
	cur = input()
	cur_rev = cur[::-1]
	for k in range(1, N):
		nxt = input()
		nxt_rev = nxt[::-1]
		if nxt < cur and nxt < cur_rev:
			tmp_ans_still = max_s
		elif nxt >= cur and nxt >= cur_rev:
			tmp_ans_still = min(ans_still, ans_rotated)
		elif nxt >= cur:
			tmp_ans_still = ans_still
		elif nxt >= cur_rev:
			tmp_ans_still = ans_rotated
		if nxt_rev < cur and nxt_rev < cur_rev:
			tmp_ans_rotated = max_s
		elif nxt_rev >= cur and nxt_rev >= cur_rev:
			tmp_ans_rotated = min(ans_still, ans_rotated) + c[k]
		elif nxt_rev >= cur:
			tmp_ans_rotated = ans_still + c[k]
		elif nxt_rev >= cur_rev:
			tmp_ans_rotated = ans_rotated + c[k]
		if tmp_ans_still >= max_s and tmp_ans_rotated >= max_s:
			return -1
		(ans_still, ans_rotated) = (tmp_ans_still, tmp_ans_rotated)
		(cur, cur_rev) = (nxt, nxt_rev)
	return min(ans_still, ans_rotated)
N = int(input())
c = list(map(int, input().split()))
print(solution(c))


import math
import sys
n = int(input())
c = list(map(int, input().split()))
f = []
for i in range(n):
	f.append(str(input()))
INF = 10 ** 18
dp = [[0], [c[0]]]
for i in range(1, n):
	dp[0].append(INF)
	if f[i] >= f[i - 1]:
		dp[0][-1] = dp[0][-2]
	if f[i] >= f[i - 1][::-1]:
		dp[0][-1] = min(dp[0][-1], dp[1][-1])
	dp[1].append(INF)
	if f[i][::-1] >= f[i - 1]:
		dp[1][-1] = dp[0][-2] + c[i]
	if f[i][::-1] >= f[i - 1][::-1]:
		dp[1][-1] = min(dp[1][-1], c[i] + dp[1][-2])
k = min(dp[0][-1], dp[1][-1])
if k >= INF:
	print(-1)
else:
	print(k)


import math

class SortObj(object):

	def __init__(self, str_obj, energy, index):
		self.str_obj = str_obj
		self.energy = energy
		self.index = index

	def __str__(self):
		return self.str_obj + ' ' + str(self.index)

	def __lt__(self, other):
		return self.str_obj < other.str_obj

	def __eq__(self, other):
		return self.str_obj == other.str_obj

	def __ge__(self, other):
		return self.str_obj >= other.str_obj

	def __gt__(self, other):
		return self.str_obj > other.str_obj

def main():
	n = int(input())
	c = [int(x) for x in input().split()]
	sort_objects = []
	for i in range(n):
		input_str = input()
		sort_objects.append(SortObj(input_str, 0, i))
		reverse_str = ''.join(reversed(input_str))
		sort_objects.append(SortObj(reverse_str, c[i], i))
	sort_objects.sort()
	problem_answer(sort_objects, n)

def problem_answer(sort_objects, n):
	total_energy = [math.inf] * n
	for sort_object in sort_objects:
		if sort_object.index == 0:
			total_energy[sort_object.index] = min(total_energy[sort_object.index], sort_object.energy)
		elif total_energy[sort_object.index - 1] == math.inf:
			pass
		else:
			total_energy[sort_object.index] = min(sort_object.energy + total_energy[sort_object.index - 1], total_energy[sort_object.index])
	if total_energy[n - 1] == math.inf:
		print(-1)
	else:
		print(total_energy[n - 1])
main()


n = int(input())
c = [int(x) for x in input().split()]
s = [input() for x in range(n)]
sr = [x[::-1] for x in s]
dp = [[0 for i in range(n)] for j in range(2)]
dp[0][0] = 0
dp[1][0] = c[0]
big = 1000000000000000
for i in range(1, n):
	if s[i] >= s[i - 1]:
		dp[0][i] = dp[0][i - 1]
	else:
		dp[0][i] = big
	if s[i] >= sr[i - 1]:
		dp[0][i] = min(dp[0][i], dp[1][i - 1])
	if sr[i] >= s[i - 1]:
		dp[1][i] = dp[0][i - 1] + c[i]
	else:
		dp[1][i] = big
	if sr[i] >= sr[i - 1]:
		dp[1][i] = min(dp[1][i], dp[1][i - 1] + c[i])
o = min(dp[0][n - 1], dp[1][n - 1])
if o == big:
	o = -1
print(o)


import sys
n = int(input())
l = list(map(int, input().split()))
a = []
dp = [[10 ** 43 for j in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = l[0]
for i in range(n):
	a.append(input())
for i in range(1, n):
	t = 0
	t1 = 0
	if a[i] >= a[i - 1]:
		t = 1
	if a[i] >= a[i - 1][::-1]:
		t1 = 1
	if t * t1 == 1:
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
	elif t == 1:
		dp[i][0] = dp[i - 1][0]
	elif t1 == 1:
		dp[i][0] = dp[i - 1][1]
	t = 0
	t1 = 0
	if a[i][::-1] >= a[i - 1]:
		t = 1
	if a[i][::-1] >= a[i - 1][::-1]:
		t1 = 1
	if t * t1 == 1:
		dp[i][1] = min(dp[i - 1][0] + l[i], dp[i - 1][1] + l[i])
	elif t == 1:
		dp[i][1] = dp[i - 1][0] + l[i]
	elif t1 == 1:
		dp[i][1] = dp[i - 1][1] + l[i]
if min(dp[n - 1][0], dp[n - 1][1]) == 10 ** 43:
	print(-1)
	sys.exit()
print(min(dp[n - 1][0], dp[n - 1][1]))


n = int(input())
s = list(map(int, input().split()))
c = []
f = 0
for i in range(n):
	c.append(input())
F = [[0, 0] for i in range(n)]
F[0][1] = s[0]
for i in range(1, n):
	if F[i - 1][0] != None and F[i - 1][1] != None and (c[i - 1] <= c[i]) and (c[i - 1][::-1] <= c[i]):
		F[i][0] = min(F[i - 1][0], F[i - 1][1])
	elif F[i - 1][0] != None and c[i - 1] <= c[i]:
		F[i][0] = F[i - 1][0]
	elif F[i - 1][1] != None and c[i - 1][::-1] <= c[i]:
		F[i][0] = F[i - 1][1]
	else:
		F[i][0] = None
		f = 1
	c1 = c[i][::-1]
	if F[i - 1][0] != None and F[i - 1][1] != None and (c[i - 1] <= c1) and (c[i - 1][::-1] <= c1):
		F[i][1] = min(F[i - 1][0], F[i - 1][1]) + s[i]
		f = 0
	elif F[i - 1][0] != None and c[i - 1] <= c1:
		F[i][1] = F[i - 1][0] + s[i]
		f = 0
	elif F[i - 1][1] != None and c[i - 1][::-1] <= c1:
		F[i][1] = F[i - 1][1] + s[i]
		f = 0
	else:
		F[i][1] = None
if f == 1:
	print(-1)
elif F[-1][0] != None and F[-1][1] != None:
	print(min(F[-1][0], F[-1][1]))
elif F[-1][0] != None:
	print(F[-1][0])
else:
	print(F[-1][1])


n = int(input())
c = list(map(int, input().split()))
s = []
for i in range(n):
	s.append(input())
rs = []
for i in range(n):
	rs.append(s[i][::-1])
D = [[0] * 2 for i in range(n)]
D[0][0] = 0
D[0][1] = c[0]
done = 0
tf = 0
for i in range(1, n):
	if D[i - 1][0] == D[i - 1][1] == -1:
		done = 1
		break
	if s[i] >= s[i - 1] and s[i] >= rs[i - 1]:
		if D[i - 1][0] != -1 and D[i - 1][1] != -1:
			D[i][0] = min(D[i - 1][0], D[i - 1][1])
		elif D[i - 1][0] != -1:
			D[i][0] = D[i - 1][0]
		elif D[i - 1][1] != -1:
			D[i][0] = D[i - 1][1]
	elif s[i] >= s[i - 1]:
		if D[i - 1][0] != -1:
			D[i][0] = D[i - 1][0]
		else:
			D[i][0] = -1
	elif s[i] >= rs[i - 1]:
		if D[i - 1][1] != -1:
			D[i][0] = D[i - 1][1]
		else:
			D[i][0] = -1
	else:
		D[i][0] = -1
	if rs[i] >= s[i - 1] and rs[i] >= rs[i - 1]:
		if D[i - 1][0] != -1 and D[i - 1][1] != -1:
			D[i][1] = c[i] + min(D[i - 1][0], D[i - 1][1])
		elif D[i - 1][0] != -1:
			D[i][1] = c[i] + D[i - 1][0]
		elif D[i - 1][1] != -1:
			D[i][1] = c[i] + D[i - 1][1]
	elif rs[i] >= s[i - 1]:
		if D[i - 1][0] != -1:
			D[i][1] = c[i] + D[i - 1][0]
		else:
			D[i][1] = -1
	elif rs[i] >= rs[i - 1]:
		if D[i - 1][1] != -1:
			D[i][1] = c[i] + D[i - 1][1]
		else:
			D[i][1] = -1
	else:
		D[i][1] = -1
if done == 1 or (D[n - 1][0] == -1 and D[n - 1][1] == -1):
	print(-1)
elif D[n - 1][0] != -1 and D[n - 1][1] != -1:
	print(min(D[n - 1][0], D[n - 1][1]))
elif D[n - 1][0] != -1:
	print(D[n - 1][0])
else:
	print(D[n - 1][1])


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		cost = ria()
		words = []
		for i in range(n):
			words.append(rs())
		dp = [[INF] * 2 for i in range(n)]
		dp[0][0] = 0
		dp[0][1] = cost[0]
		ans = 0
		prevword = words[0]
		prevwordrev = words[0][::-1]
		for i in range(1, n):
			(currword, currwordrev) = (words[i], words[i][::-1])
			if currword >= prevword:
				dp[i][0] = min(dp[i][0], dp[i - 1][0])
			if prevwordrev <= currword:
				dp[i][0] = min(dp[i][0], dp[i - 1][1])
			if currwordrev >= prevword:
				dp[i][1] = min(dp[i][1], cost[i] + dp[i - 1][0])
			if prevwordrev <= currwordrev:
				dp[i][1] = min(dp[i][1], cost[i] + dp[i - 1][1])
			(prevword, prevwordrev) = (currword, currwordrev)
	ans = min(dp[n - 1][0], dp[n - 1][1])
	ans = ans if ans != INF else -1
	print(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


oo = 10 ** 15
n = int(input())
a = list(map(int, input().split()))
sol = rsol = 0
last = rlast = ''
for i in range(n):
	w = input()
	rw = w[::-1]
	curr = rcurr = oo
	if w >= last:
		curr = min(curr, sol)
	if w >= rlast:
		curr = min(curr, rsol)
	if rw >= last:
		rcurr = min(rcurr, sol + a[i])
	if rw >= rlast:
		rcurr = min(rcurr, rsol + a[i])
	(last, rlast) = (w, rw)
	(sol, rsol) = (curr, rcurr)
sol = min(sol, rsol)
if sol >= oo:
	print(-1)
else:
	print(sol)


n = int(input())
c = list(map(int, input().split()))
pw = input()
prw = pw[::-1]
r = [0, c[0]]
inf = float('inf')
for i in range(1, n):
	w = input()
	rw = w[::-1]
	ro = inf
	rro = inf
	if w >= pw:
		ro = min(r[0], ro)
	if w >= prw:
		ro = min(r[1], ro)
	if rw >= pw:
		rro = min(r[0], rro)
	if rw >= prw:
		rro = min(r[1], rro)
	r = [ro, rro + c[i]]
	(pw, prw) = (w, rw)
r = min(r)
if r < inf:
	print(r)
else:
	print(-1)


def swap(mot):
	return mot[::-1]

def comparer_mots(mot1, mot2):
	if mot1 == mot2:
		return 0
	if len(mot1) < len(mot2) and mot1 == mot2[:len(mot1)]:
		return -1
	if len(mot2) < len(mot1) and mot2 == mot1[:len(mot2)]:
		return 1
	for x in range(len(mot1)):
		if mot1[x] < mot2[x]:
			return -1
		elif mot2[x] < mot1[x]:
			return 1
n = int(input())
c = [int(x) for x in input().split()]
mot2 = input()
dpU = [0] * n
dpR = [0] * n
dpU[0] = 0
dpR[0] = c[0]
for x in range(1, n):
	mot1 = mot2
	mot2 = input()
	if comparer_mots(mot1, mot2) <= 0 and comparer_mots(swap(mot1), mot2) <= 0:
		if dpU[x - 1] <= dpR[x - 1]:
			dpU[x] = dpU[x - 1]
		else:
			dpU[x] = dpR[x - 1]
	elif comparer_mots(mot1, mot2) <= 0:
		dpU[x] = dpU[x - 1]
	elif comparer_mots(swap(mot1), mot2) <= 0:
		dpU[x] = dpR[x - 1]
	else:
		dpU[x] = 10 ** 15
	if comparer_mots(mot1, swap(mot2)) <= 0 and comparer_mots(swap(mot1), swap(mot2)) <= 0:
		if dpU[x - 1] <= dpR[x - 1]:
			dpR[x] = dpU[x - 1] + c[x]
		else:
			dpR[x] = dpR[x - 1] + c[x]
	elif comparer_mots(mot1, swap(mot2)) <= 0:
		dpR[x] = dpU[x - 1] + c[x]
	elif comparer_mots(swap(mot1), swap(mot2)) <= 0:
		dpR[x] = dpR[x - 1] + c[x]
	else:
		dpR[x] = 10 ** 15
cout = min(dpU[n - 1], dpR[n - 1])
if cout >= 10 ** 15:
	print(-1)
else:
	print(cout)


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
INF = int(1e+18)
n = II()
c = LI()
s = []
for _ in range(n):
	s.append(SI())
dp = [[INF for i in range(2)] for j in range(n)]
dp[0][1] = c[0]
dp[0][0] = 0
for i in range(1, n):
	if s[i] >= s[i - 1]:
		dp[i][0] = dp[i - 1][0]
	if s[i][::-1] >= s[i - 1]:
		dp[i][1] = dp[i - 1][0] + c[i]
	if s[i] >= s[i - 1][::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if s[i][::-1] >= s[i - 1][::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
print(min(dp[-1]) if min(dp[-1]) != INF else -1)


n = int(input())
A = list(map(int, input().split()))
B = []
for i in range(n):
	s = str(input())
	B.append(s)
dp1 = [0] * n
dp2 = [0] * n
dp2[0] = A[0]

def lex(a, b):
	for i in range(min(len(a), len(b))):
		if a[i] != b[i]:
			if ord(a[i]) > ord(b[i]):
				return True
			else:
				return False
	if len(a) >= len(b):
		return True
	else:
		return False
for i in range(1, n):
	c = B[i]
	p = B[i - 1]
	cr = c[::-1]
	pr = p[::-1]
	if dp1[i - 1] == -1 and dp2[i - 1] == -1:
		dp1[i] = -1
		dp2[i] = -1
	elif dp1[i - 1] == -1:
		if lex(c, pr):
			dp1[i] = dp2[i - 1]
		else:
			dp1[i] = -1
		if lex(cr, pr):
			dp2[i] = dp2[i - 1] + A[i]
		else:
			dp2[i] = -1
	elif dp2[i - 1] == -1:
		if lex(c, p):
			dp1[i] = dp1[i - 1]
		else:
			dp1[i] = -1
		if lex(cr, p):
			dp2[i] = dp1[i - 1] + A[i]
		else:
			dp2[i] = -1
	else:
		if lex(c, p):
			if lex(c, pr):
				dp1[i] = min(dp1[i - 1], dp2[i - 1])
			else:
				dp1[i] = dp1[i - 1]
		elif lex(c, pr):
			dp1[i] = dp2[i - 1]
		else:
			dp1[i] = -1
		if lex(cr, p):
			if lex(cr, pr):
				dp2[i] = min(dp1[i - 1], dp2[i - 1]) + A[i]
			else:
				dp2[i] = dp1[i - 1] + A[i]
		elif lex(cr, pr):
			dp2[i] = dp2[i - 1] + A[i]
		else:
			dp2[i] = -1
if dp1[n - 1] != -1 and dp2[n - 1] != -1:
	print(min(dp1[n - 1], dp2[n - 1]))
else:
	print(max(dp1[n - 1], dp2[n - 1]))


def b3_hard_problems(n, c, s, t):
	l = r = ''
	a = b = 0
	for i in range(n):
		x = y = 10 ** 16
		if s[i] >= l:
			x = a
		if s[i] >= r:
			x = min(x, b)
		if t[i] >= l:
			y = a + c[i]
		if t[i] >= r:
			y = min(y, b + c[i])
		l = s[i]
		r = t[i]
		a = x
		b = y
	a = min(a, b)
	if a == 10 ** 16:
		a = -1
	return a
n = int(input())
a = list(map(int, input().split()))
s = []
t = []
for i in range(n):
	s1 = input()
	t1 = s1[::-1]
	s.append(s1)
	t.append(t1)
result = b3_hard_problems(n, a, s, t)
print(result)


from math import inf
n = int(input())
l = [int(i) for i in input().split()]
s = []
for i in range(n):
	s.append(input())
(x, y) = (0, l[0])
for i in range(1, n):
	prev = s[i - 1]
	rprev = prev[::-1]
	curr = s[i]
	rcurr = curr[::-1]
	(xx, yy) = (inf, inf)
	if curr >= prev:
		xx = x
	if curr >= rprev:
		xx = min(y, xx)
	if rcurr >= prev:
		yy = x + l[i]
	if rcurr >= rprev:
		yy = min(yy, y + l[i])
	(x, y) = (xx, yy)
ans = min(x, y)
ans = -1 if ans == inf else ans
print(ans)


inf = 10 ** 15
n = int(input())
w = list(map(int, input().split()))
s = [input() for i in range(n)]
sr = [x[::-1] for x in s]
cost = [[0, w[i]] for i in range(n)]
for i in range(1, n):
	tmp = inf
	if s[i] >= s[i - 1]:
		tmp = min(tmp, cost[i - 1][0])
	if s[i] >= sr[i - 1]:
		tmp = min(tmp, cost[i - 1][1])
	cost[i][0] = tmp
	tmp = inf
	if sr[i] >= s[i - 1]:
		tmp = min(tmp, cost[i - 1][0])
	if sr[i] >= sr[i - 1]:
		tmp = min(tmp, cost[i - 1][1])
	cost[i][1] = tmp + w[i]
ans = min(cost[-1][0], cost[-1][1])
if ans >= inf:
	print(-1)
else:
	print(ans)


import sys
import math
import collections
import heapq
n = int(input())
c = [int(i) for i in input().split()]
m = 10000000000000000
dp = []
for i in range(n + 1):
	l1 = [m, m]
	dp.append(l1)
(dp[0][0], dp[0][1]) = (0, 0)
prev1 = ''
prev2 = ''
c1 = 1
s = 0
for i in range(n):
	s1 = input()
	s2 = s1[::-1]
	c2 = 0
	if s1 >= prev1:
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][0])
		c2 = 1
	if s1 >= prev2:
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][1])
		c2 = 1
	if s2 >= prev1:
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + c[i])
		c2 = 1
	if s2 >= prev2:
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + c[i])
		c2 = 1
	if c2 == 0:
		c1 = 0
		break
	else:
		prev1 = s1
		prev2 = s2
if c1 == 0 or min(dp[n][0], dp[n][1]) == 10000000000000000:
	print(-1)
else:
	print(min(dp[n][0], dp[n][1]))


input = __import__('sys').stdin.buffer.readline
oo = 10 ** 15
n = int(input())
a = list(map(int, input().split()))
sol = rsol = 0
last = rlast = ''
for i in range(n):
	w = input().decode().strip()
	rw = w[::-1]
	curr = rcurr = oo
	if w >= last:
		curr = min(curr, sol)
	if w >= rlast:
		curr = min(curr, rsol)
	if rw >= last:
		rcurr = min(rcurr, sol + a[i])
	if rw >= rlast:
		rcurr = min(rcurr, rsol + a[i])
	(last, rlast) = (w, rw)
	(sol, rsol) = (curr, rcurr)
sol = min(sol, rsol)
if sol >= oo:
	print(-1)
else:
	print(sol)


from sys import stdin

def reverse(string):
	return string[::-1]
n = int(stdin.readline().strip())
cost = list(map(int, stdin.readline().split()))
dp = [[float('inf') for x in range(2)] for x in range(n)]
prev = stdin.readline().strip()
dp[0][0] = 0
dp[0][1] = cost[0]
for i in range(1, n):
	cur = stdin.readline().strip()
	if cur >= prev:
		dp[i][0] = min(dp[i - 1][0], dp[i][0])
	if cur >= reverse(prev):
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if reverse(cur) >= prev:
		dp[i][1] = min(dp[i - 1][0] + cost[i], dp[i][1])
	if reverse(cur) >= reverse(prev):
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i])
	prev = cur
if dp[n - 1][0] == float('inf') and dp[n - 1][1] == float('inf'):
	print(-1)
else:
	print(min(dp[n - 1]))


import sys
input = sys.stdin.readline
n = int(input())
c = list(map(int, input().split()))
INF = 10 ** 18
dp0 = [INF] * n
dp1 = [INF] * n
dp0[0] = 0
dp1[0] = c[0]
b0 = input().strip()
b1 = b0[::-1]
for i in range(1, n):
	a0 = b0
	a1 = b1
	b0 = input().strip()
	b1 = b0[::-1]
	if a0 <= b0:
		dp0[i] = min(dp0[i], dp0[i - 1])
	if a1 <= b0:
		dp0[i] = min(dp0[i], dp1[i - 1])
	if a0 <= b1:
		dp1[i] = min(dp1[i], dp0[i - 1] + c[i])
	if a1 <= b1:
		dp1[i] = min(dp1[i], dp1[i - 1] + c[i])
ans = min(dp0[n - 1], dp1[n - 1])
if ans == INF:
	ans = -1
print(ans)


n = int(input())
c = list(map(int, input().split()))
from sys import stdin
res = [[1000000000000000000, 1000000000000000000] for i in range(n)]
y = input()
length2 = len(y)
(res[0][0], res[0][1]) = (0, c[0])
(y1, y2) = (y, y[::-1])
for i in range(1, n):
	x = stdin.readline()[:-1]
	length1 = len(x)
	for j in range(2):
		if j == 1:
			x = x[::-1]
		if length1 < length2:
			if y1[:length2] == x or y2[:length2] == x:
				res[i][j] = -1
				continue
		if x >= y1 and res[i - 1][0] > -1:
			res[i][j] = min(res[i][j], res[i - 1][0] + c[i] * j)
		if x >= y2 and res[i - 1][1] > -1:
			res[i][j] = min(res[i][j], res[i - 1][1] + c[i] * j)
	(y1, y2) = (x[::-1], x)
	length2 = length1
result = min(res[n - 1][0], res[n - 1][1])
if result == 1000000000000000000:
	result = -1
print(result)


a = int(input())
qw = [int(i) for i in input().split()]
p = input()
now = [[0, p], [qw[0], p[::-1]]]
for u in range(1, a):
	inp = input()
	er1 = [[], []]
	for i in now:
		if sorted([i[1], inp]) == [i[1], inp]:
			er1[0].append(i[0])
		if sorted([i[1], inp[::-1]]) == [i[1], inp[::-1]]:
			er1[1].append(i[0] + qw[u])
	now = []
	if len(er1[0]) != 0:
		now.append([min(er1[0]), inp])
	if len(er1[1]) != 0:
		now.append([min(er1[1]), inp[::-1]])
	if len(er1[1]) == 0 and len(er1[0]) == 0:
		print(-1)
		exit()
minn = 10 ** 15
for i in now:
	minn = min(minn, i[0])
print(minn)


n = int(input())
ene = list(map(int, input().split()))
txt = [input() for _ in range(n)]
dp = [[10 ** 19 for _ in range(2)] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = ene[0]
for i in range(1, n):
	if txt[i] >= txt[i - 1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if txt[i] >= txt[i - 1][::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if txt[i][::-1] >= txt[i - 1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + ene[i])
	if txt[i][::-1] >= txt[i - 1][::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + ene[i])
ans = min(dp[-1])
if ans == 10 ** 19:
	print(-1)
else:
	print(ans)


I = input
n = int(I())
C = list(map(int, I().split()))
prev = ''
c = c_s = 0
for i in range(n):
	s = I()
	x = y = 10 ** 15
	if s >= prev:
		x = c
	if s >= prev[::-1]:
		x = min(x, c_s)
	if s[::-1] >= prev:
		y = c + C[i]
	if s[::-1] >= prev[::-1]:
		y = min(y, c_s + C[i])
	c = x
	c_s = y
	prev = s
ans = min(c, c_s)
if ans == 10 ** 15:
	ans = -1
print(ans)


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep=' ', end='\n'):
	print(*var, file=sys.stderr, end=end, sep=sep)
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
cost = I()
ans = 0
previous = ''
dp = [[INF] * 2 for i in range(n + 1)]
dp[0] = [0, 0]
for i in range(n):
	s = input()
	if s >= previous:
		dp[i + 1][0] = dp[i][0]
	if s >= previous[::-1]:
		dp[i + 1][0] = min(dp[i + 1][0], dp[i][1])
	s = s[::-1]
	if s >= previous:
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][0] + cost[i])
	if s >= previous[::-1]:
		dp[i + 1][1] = min(dp[i + 1][1], dp[i][1] + cost[i])
	previous = s[::-1]
if dp[n][0] >= INF and dp[n][1] >= INF:
	print(-1)
	exit()
print(min(dp[n]))


n = int(input())
c = list(map(int, input().split()))
dp = [[float('Inf'), float('Inf')] for _ in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
s1 = input()
r1 = s1[::-1]
for i in range(1, n):
	s2 = input()
	r2 = s2[::-1]
	if r1 <= s2:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if r1 <= r2:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	if s1 <= s2:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if s1 <= r2:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
	s1 = s2
	r1 = r2
if float('Inf') == min(dp[n - 1]):
	print(-1)
else:
	print(min(dp[n - 1]))


n = int(input())
cost = []
cost = input()
cost = cost.split(' ')
for i in range(n):
	cost[i] = int(cost[i])
prev = input()
left = []
right = []
left.append(0)
right.append(cost[0])
for i in range(1, n):
	curr = input()
	if left[i - 1] == -1 and right[i - 1] == -1:
		left.append(-1)
		right.append(-1)
	elif left[i - 1] >= 0 and right[i - 1] == -1:
		if curr >= prev:
			left.append(left[i - 1])
		else:
			left.append(-1)
		if curr[::-1] >= prev:
			right.append(left[i - 1] + cost[i])
		else:
			right.append(-1)
	elif left[i - 1] == -1 and right[i - 1] >= 0:
		if curr >= prev[::-1]:
			left.append(right[i - 1])
		else:
			left.append(-1)
		if curr[::-1] >= prev[::-1]:
			right.append(right[i - 1] + cost[i])
		else:
			right.append(-1)
	else:
		if curr >= prev and curr >= prev[::-1]:
			left.append(min(left[i - 1], right[i - 1]))
		elif curr >= prev:
			left.append(left[i - 1])
		elif curr >= prev[::-1]:
			left.append(right[i - 1])
		else:
			left.append(-1)
		if curr[::-1] >= prev and curr[::-1] >= prev[::-1]:
			right.append(min(left[i - 1], right[i - 1]) + cost[i])
		elif curr[::-1] >= prev:
			right.append(left[i - 1] + cost[i])
		elif curr[::-1] >= prev[::-1]:
			right.append(right[i - 1] + cost[i])
		else:
			right.append(-1)
	prev = curr[:]
if left[n - 1] >= 0 and right[n - 1] >= 0:
	print(min(left[n - 1], right[n - 1]))
elif left[n - 1] >= 0:
	print(left[n - 1])
else:
	print(right[n - 1])


n = int(input())
c = list(map(int, input().split()))
f = [0 for i in range(n)]
g = [0 for i in range(n)]
a = input()
f[0] = c[0]
g[0] = 0
for i in range(1, n):
	b = input()
	l = a[::-1]
	r = b[::-1]
	if a <= b and l <= b and (f[i - 1] != -1) and (g[i - 1] != -1):
		g[i] = min(f[i - 1], g[i - 1])
	elif a <= b and g[i - 1] != -1:
		g[i] = g[i - 1]
	elif l <= b and f[i - 1] != -1:
		g[i] = f[i - 1]
	else:
		g[i] = -1
	if a <= r and l <= r and (f[i - 1] != -1) and (g[i - 1] != -1):
		f[i] = min(f[i - 1], g[i - 1]) + c[i]
	elif a <= r and g[i - 1] != -1:
		f[i] = g[i - 1] + c[i]
	elif l <= r and f[i - 1] != -1:
		f[i] = f[i - 1] + c[i]
	else:
		f[i] = -1
	a = b
if f[n - 1] != -1 and g[n - 1] != -1:
	print(min(f[n - 1], g[n - 1]))
else:
	print(max(f[n - 1], g[n - 1]))


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	(n,) = aj()
	P = aj()
	S = []
	for i in range(n):
		S.append(input())
	dp = [[0, 0] for i in range(n)]
	oprev = S[0]
	cprev = S[0][::-1]
	dp[0][1] = P[0]
	inf = float('inf')
	for i in range(1, n):
		s = S[i]
		t = S[i][::-1]
		(a, b) = (inf, inf)
		if s >= oprev:
			a = dp[i - 1][0]
		if s >= cprev:
			b = dp[i - 1][1]
		dp[i][0] = min(a, b)
		(a, b) = (inf, inf)
		if t >= oprev:
			a = dp[i - 1][0]
		if t >= cprev:
			b = dp[i - 1][1]
		dp[i][1] = min(a, b) + P[i]
		oprev = s
		cprev = t
	ans = min(dp[-1])
	if ans == inf:
		print(-1)
	else:
		print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
solve()


n = int(input())
c = [int(x) for x in input().split()]
l = []
for _ in range(n):
	l.append(str(input()))
dp = [[10 ** 18] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
ans = 10 ** 18
for i in range(1, n):
	if min(l[i - 1], l[i - 1][::-1]) > max(l[i], l[i][::-1]):
		ans = -1
		break
	if l[i - 1] <= l[i]:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if l[i - 1][::-1] <= l[i]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if l[i - 1] <= l[i][::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
	if l[i - 1][::-1] <= l[i][::-1]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	ans = min(dp[i][0], dp[i][1])
print(ans if ans != 10 ** 18 else -1)


import sys
n = int(input())
cs = list(map(int, input().split()))
ss = []
for i in range(n):
	ss += [input()]
a = ss[0]
ac = 0
b = ss[0][::-1]
bc = cs[0]
imp1 = False
imp2 = False
for i in range(1, len(ss)):
	nimp1 = False
	nimp2 = False
	s = ss[i]
	if not imp1 and (not imp2) and (s >= a) and (s >= b):
		na = s
		nac = min(ac, bc)
	elif not imp1 and s >= a:
		na = s
		nac = ac
	elif not imp2 and s >= b:
		na = s
		nac = bc
	else:
		nimp1 = True
	r = s[::-1]
	if not imp1 and (not imp2) and (r >= a) and (r >= b):
		nb = r
		nbc = min(ac, bc) + cs[i]
	elif not imp1 and r >= a:
		nb = r
		nbc = ac + cs[i]
	elif not imp2 and r >= b:
		nb = r
		nbc = bc + cs[i]
	else:
		nimp2 = True
	if nimp1 and nimp2:
		print(-1)
		sys.exit()
	if not nimp1:
		a = na
		ac = nac
	if not nimp2:
		b = nb
		bc = nbc
	imp1 = nimp1
	imp2 = nimp2
if imp1:
	print(bc)
elif imp2:
	print(ac)
else:
	print(min(ac, bc))


INF = 100000000000001
n = int(input())
cost = list(map(int, input().split()))
words = [input() for i in range(n)]
rev_words = [s[::-1] for s in words]
dp = [[INF, INF] for i in range(n)]
dp[0][0] = 0
dp[0][1] = cost[0]
for i in range(1, n):
	if words[i - 1] <= words[i]:
		dp[i][0] = dp[i - 1][0]
	if rev_words[i - 1] <= words[i]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if words[i - 1] <= rev_words[i]:
		dp[i][1] = dp[i - 1][0] + cost[i]
	if rev_words[i - 1] <= rev_words[i]:
		dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i])
res = min(dp[n - 1][0], dp[n - 1][1])
res = -1 if res == INF else res
print(res)


I = input
(n, C, d) = (int(I()), list(map(int, I().split())), {'': 0})
for i in range(n):
	if not d:
		print(-1)
		break
	(s, tmp) = (I(), {})
	for (s, c) in ((s, 0), (s[::-1], C[i])):
		for (prev, val) in d.items():
			if prev <= s and (s not in tmp or tmp[s] > val + c):
				tmp[s] = val + c
	d = tmp
else:
	print(min(d.values()) if d else -1)


from sys import stdin, stdout
MX = 10 ** 15 + 5
n = int(stdin.readline())
c = []
c = list(map(int, input().split(' ')))
s = []
for i in range(n):
	s.append(input())
dp = []
for i in range(n):
	dp.append([0, c[i]])
flag = True
for i in range(1, n):
	mn1 = MX
	if s[i - 1] <= s[i] and dp[i - 1][0] >= 0:
		mn1 = min(mn1, dp[i - 1][0])
	if s[i - 1][::-1] <= s[i] and dp[i - 1][1] >= 0:
		mn1 = min(mn1, dp[i - 1][1])
	mn2 = MX
	if s[i - 1] <= s[i][::-1] and dp[i - 1][0] >= 0:
		mn2 = min(mn2, dp[i - 1][0])
	if s[i - 1][::-1] <= s[i][::-1] and dp[i - 1][1] >= 0:
		mn2 = min(mn2, dp[i - 1][1])
	if mn1 >= MX and mn2 >= MX:
		flag = False
		break
	if mn2 < MX:
		dp[i][1] += mn2
	else:
		dp[i][1] = -1
	if mn1 < MX:
		dp[i][0] += mn1
	else:
		dp[i][0] = -1
ans = min(dp[-1][0], dp[-1][1])
if ans < 0:
	ans = max(dp[-1][0], dp[-1][1])
if flag:
	stdout.write(str(ans))
else:
	stdout.write(str(-1))


n = int(input())
c = [int(x) for x in input().split()]
s1 = input()
(c1, c2) = (0, c[0])
for i in range(1, n):
	s = input()
	(nc1, nc2) = (None, None)
	if c1 is not None:
		if s >= s1:
			nc1 = c1
		if s[::-1] >= s1:
			nc2 = c1 + c[i]
	if c2 is not None:
		if s >= s1[::-1] and (nc1 is None or c2 < nc1):
			nc1 = c2
		if s[::-1] >= s1[::-1] and (nc2 is None or c2 + c[i] < nc2):
			nc2 = c2 + c[i]
	(c1, c2) = (nc1, nc2)
	if c1 is None and c2 is None:
		break
	s1 = s
if c1 is not None and c2 is not None:
	print(min(c1, c2))
elif c1 is not None:
	print(c1)
elif c2 is not None:
	print(c2)
else:
	print(-1)


import os
import sys
from bisect import bisect_right
from collections import Counter
from io import BytesIO, IOBase
from math import gcd, inf, sqrt

def lcm(a, b):
	return a * b // gcd(a, b)

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def cheaker(a):
	j = 1
	p = False
	for i in a:
		if i != j:
			break
		j += 1
	q = len(a)
	for i in a[::-1]:
		if i != q:
			break
		q -= 1
	for i in range(j - 1, q):
		if a[i] == i + 1:
			return False
	return True

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	n = int(input())
	a = [int(c) for c in input().split()]
	s = []
	for i in range(n):
		x = input().strip()
		s.append(x)
	dp = [[inf, inf] for i in range(n)]
	dp[0] = [0, a[0]]
	for i in range(1, n):
		if s[i] >= s[i - 1]:
			dp[i][0] = min(dp[i - 1][0], dp[i][0])
		if s[i] >= s[i - 1][::-1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if s[i][::-1] >= s[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + a[i])
		if s[i][::-1] >= s[i - 1][::-1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + a[i])
	print(min(dp[-1]) if min(dp[-1]) != inf else -1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
x = input().split()
c = list((int(x[i]) for i in range(len(x))))
fail = 1000000000000000000000000
s = []
for i in range(n):
	s.append(input())

def start(st, e, n):
	if st < n:
		s1 = s[st][::-1]
		if st == 0:
			if s1 < s[st]:
				e[0] = e[0] + c[st]
			else:
				e[1] = fail
		else:
			s2 = s[st - 1][::-1]
			if max(s1, s[st]) < min(s2, s[st - 1]):
				e[0] = e[1] = fail
			elif min(s1, s[st]) < min(s2, s[st - 1]) and max(s1, s[st]) >= min(s2, s[st - 1]):
				if s1 > s[st]:
					if s1 < max(s2, s[st - 1]):
						e[1] = e[0] + c[st]
					else:
						e[1] = min(e[0], e[1]) + c[st]
				elif s[st] < max(s2, s[st - 1]):
					e[1] = e[0]
				else:
					e[1] = min(e[0], e[1])
				e[0] = fail
			elif min(s1, s[st]) >= min(s2, s[st - 1]):
				if max(s2, s[st - 1]) > max(s1, s[st]):
					if e[0] >= fail:
						e[1] = fail
					elif s1 < s[st]:
						e[1] = e[0]
						e[0] = e[0] + c[st]
					else:
						e[1] = fail
				elif min(s1, s[st]) >= max(s2, s[st - 1]):
					if s1 < s[st]:
						e[1] = min(e[0], e[1])
						e[0] = e[1] + c[st]
					else:
						e[0] = min(e[0], e[1])
						e[1] = fail
				elif e[1] >= fail:
					if s1 < s[st]:
						e[1] = e[0]
						e[0] = e[0] + c[st]
				elif e[0] >= fail:
					if s1 > s[st]:
						e[1] = e[1] + c[st]
				elif s1 <= s[st]:
					e[0] = e[0] + c[st]
				elif e[1] + c[st] < e[0]:
					e[1] = e[1] + c[st]
				else:
					e[1] = fail
	return e
e = [0, 0]
for i in range(n):
	if min(e[0], e[1]) >= fail:
		break
	e = start(i, e, n)
m = min(e[0], e[1])
print(-1 if m >= fail else m)


I = input
n = int(I())
c = list(map(int, I().split()))
l = r = ''
a = b = 0
for i in range(n):
	s = I()
	t = s[::-1]
	x = y = 10 ** 16
	if s >= l:
		x = a
	if s >= r:
		x = min(x, b)
	if t >= l:
		y = a + c[i]
	if t >= r:
		y = min(y, b + c[i])
	l = s
	r = t
	a = x
	b = y
a = min(a, b)
if a == 10 ** 16:
	a = -1
print(a)


n = int(input())
v = list(map(int, input().split()))
s = []
for i in range(n):
	q = input()
	l = []
	l.append(q)
	l.append(''.join(reversed(q)))
	s.append(l)
dp = [[1e+18 for i in range(2)] for j in range(n)]
flag = 1
dp[0][0] = 0
dp[0][1] = v[0]
for i in range(1, n):
	if dp[i - 1][0] == -1 and dp[i - 1][1] == -1:
		flag = 0
		break
	if dp[i - 1][0] != -1:
		if s[i][0] >= s[i - 1][0]:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if s[i][1] >= s[i - 1][0]:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + v[i])
	if dp[i - 1][1] != -1:
		if s[i][0] >= s[i - 1][1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if s[i][1] >= s[i - 1][1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + v[i])
	if dp[i][0] == 1e+18:
		dp[i][0] = -1
	if dp[i][1] == 1e+18:
		dp[i][1] = -1
if flag == 0:
	print(-1)
elif dp[n - 1][0] != -1 and dp[n - 1][1] != -1:
	print(min(dp[n - 1][1], dp[n - 1][0]))
elif dp[n - 1][1] != -1:
	print(dp[n - 1][1])
else:
	print(dp[n - 1][0])


import math
n = int(input())
c = list(map(int, input().split()))
dp = [[math.inf, math.inf] for _ in range(n)]
for i in range(n):
	if i == 0:
		prev = input()
		dp[i][0] = 0
		dp[i][1] = c[i]
	else:
		current = input()
		if current >= prev:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if current >= prev[::-1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if current[::-1] >= prev:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
		if current[::-1] >= prev[::-1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
		prev = current
ans = min(dp[n - 1][0], dp[n - 1][1])
if ans == math.inf:
	print(-1)
else:
	print(ans)


from sys import stdin, stdout
n = int(input())
c = [int(x) for x in input().split()]
s = []
for i in range(n):
	ne = input()
	ne = ne.rstrip()
	s.append(ne)
dp = [[-1, -1] for i in range(n)]
dp[0] = [0, c[0]]
for i in range(1, n):
	s1 = s[i - 1]
	s2 = s1[::-1]
	s3 = s[i]
	s4 = s3[::-1]
	if s3 >= s1 and dp[i - 1][0] != -1:
		dp[i][0] = dp[i - 1][0]
	if s3 >= s2 and dp[i - 1][1] != -1:
		if dp[i][0] != -1:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		else:
			dp[i][0] = dp[i - 1][1]
	if s4 >= s1 and dp[i - 1][0] != -1:
		dp[i][1] = dp[i - 1][0] + c[i]
	if s4 >= s2 and dp[i - 1][1] != -1:
		if dp[i][1] == -1:
			dp[i][1] = dp[i - 1][1] + c[i]
		else:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
if dp[n - 1][0] == -1 or dp[n - 1][1] == -1:
	print(str(dp[n - 1][0] + dp[n - 1][1] + 1))
else:
	print(str(min(dp[n - 1][0], dp[n - 1][1])))


from sys import stdin
from collections import *

def arr_inp(n):
	if n == 1:
		return [int(x) for x in stdin.readline().split()]
	elif n == 2:
		return [float(x) for x in stdin.readline().split()]
	else:
		return list(stdin.readline()[:-1])
(n, c) = (int(input()), arr_inp(1))
(s, mem) = ([input() for i in range(n)], defaultdict(lambda : float('inf'), {(0, 0): 0, (0, 1): c[0]}))
for i in range(1, n):
	if s[i] >= s[i - 1]:
		mem[i, 0] = min(mem[i, 0], mem[i - 1, 0])
	if s[i] >= s[i - 1][::-1]:
		mem[i, 0] = min(mem[i, 0], mem[i - 1, 1])
	if s[i][::-1] >= s[i - 1]:
		mem[i, 1] = min(mem[i, 1], c[i] + mem[i - 1, 0])
	if s[i][::-1] >= s[i - 1][::-1]:
		mem[i, 1] = min(mem[i, 1], c[i] + mem[i - 1, 1])
mi = min(mem[n - 1, 1], mem[n - 1, 0])
print(mi if mi != float('inf') else -1)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def main():
	n = I()
	a = LI()
	aa = [S() for _ in range(n)]
	dp = [0, 0]
	t = ''
	tr = ''
	for i in range(n):
		s = aa[i]
		np = [inf, inf]
		if t <= s:
			np[0] = dp[0]
		if tr <= s and np[0] > dp[1]:
			np[0] = dp[1]
		sr = s[::-1]
		if t <= sr:
			np[1] = dp[0] + a[i]
		if tr <= sr and np[1] > dp[1] + a[i]:
			np[1] = dp[1] + a[i]
		t = s
		tr = sr
		dp = np
	r = min(dp)
	if r >= inf:
		return -1
	return r
print(main())


n = int(input())
c = list(map(int, input().split()))
b = []
d = []
for i in range(n):
	x = input()
	b.append(x)
	d.append(x[::-1])
dp = []
for i in range(n):
	dp.append([float('inf'), float('inf')])
dp[-1][0] = 0
dp[-1][1] = c[-1]
i = n - 2
while i >= 0:
	if b[i] <= b[i + 1]:
		dp[i][0] = min(dp[i][0], dp[i + 1][0])
	if b[i] <= d[i + 1]:
		dp[i][0] = min(dp[i][0], dp[i + 1][1])
	if d[i] <= b[i + 1]:
		dp[i][1] = min(dp[i][1], dp[i + 1][0] + c[i])
	if d[i] <= d[i + 1]:
		dp[i][1] = min(dp[i][1], dp[i + 1][1] + c[i])
	i += -1
k = min(dp[0][0], dp[0][1])
if k == float('inf'):
	print(-1)
else:
	print(k)


import sys, math
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
import collections as col
import math

def solve():
	N = getInt()
	C = getInts()
	dp = [[10 ** 18 for j in range(2)] for i in range(N)]
	dp[0][0] = 0
	dp[0][1] = C[0]
	max_val = 10 ** 18
	strings = []
	for n in range(N):
		zz = listStr()
		strings.append((''.join(zz), ''.join(zz[::-1])))
	for j in range(1, N):
		if strings[j][0] >= strings[j - 1][0]:
			dp[j][0] = dp[j - 1][0]
		if strings[j][0] >= strings[j - 1][1]:
			dp[j][0] = min(dp[j][0], dp[j - 1][1])
		if strings[j][1] >= strings[j - 1][0]:
			dp[j][1] = dp[j - 1][0] + C[j]
		if strings[j][1] >= strings[j - 1][1]:
			dp[j][1] = min(dp[j][1], dp[j - 1][1] + C[j])
	ans = min(dp[N - 1][0], dp[N - 1][1])
	if ans > 10 ** 17:
		return -1
	return ans
print(solve())


from collections import defaultdict

def can(spots, sum):
	return 9 * spots >= sum

def biggest(m, s):
	if m == 1 and s <= 9:
		return str(s)
	if m == 1 and s >= 10:
		return 'x'
	if m > 1:
		mx = min(9, s)
		return str(mx) + biggest(m - 1, s - mx)
	return 'x'

def smallest(m, s):
	res = ''
	for i in range(m):
		for digit in range(0, 11):
			if (i > 0 or digit > 0 or (m == 1 and digit == 0)) and can(m - i - 1, s - digit):
				res += str(digit)
				s = s - digit
				break
	return res

def main():
	dp = defaultdict(lambda : float('inf'))
	n = int(input())
	costs = [int(i) for i in input().split()]
	s = []
	for _ in range(n):
		string = input()
		s.append(string)
	dp[0, 0] = 0
	dp[0, 1] = costs[0]
	for i in range(1, n):
		if s[i] >= s[i - 1]:
			dp[i, 0] = dp[i - 1, 0]
		if s[i] >= s[i - 1][::-1]:
			dp[i, 0] = min(dp[i, 0], dp[i - 1, 1])
		rev = s[i][::-1]
		if rev >= s[i - 1]:
			dp[i, 1] = costs[i] + dp[i - 1, 0]
		if rev >= s[i - 1][::-1]:
			dp[i, 1] = min(dp[i, 1], costs[i] + dp[i - 1, 1])
	res = min(dp[n - 1, 1], dp[n - 1, 0])
	if res == float('inf'):
		print(-1)
	else:
		print(res)
main()


def cmp(s, t):
	A = s <= t
	(sr, tr) = (s[::-1], t[::-1])
	B = sr <= t
	C = s <= tr
	D = sr <= tr
	return (A, B, C, D)
INFTY = 10 ** 15
(n,) = map(int, input().split())
cost = list(map(int, input().split()))
prev = input()
coststr = 0
costrrev = cost[0]
fail = False
for i in range(1, n):
	curr = input()
	(a, b, c, d) = cmp(prev, curr)
	(c1, c2) = (INFTY, INFTY)
	if a:
		c1 = min(c1, coststr)
	if b:
		c1 = min(c1, costrrev)
	if c:
		c2 = min(c2, coststr + cost[i])
	if d:
		c2 = min(c2, costrrev + cost[i])
	if c1 >= INFTY and c2 >= INFTY:
		fail = True
		break
	(coststr, costrrev) = (c1, c2)
	prev = curr
if fail:
	print(-1)
else:
	print(min(coststr, costrrev))


inf = float('inf')
n = int(input())
c = [int(x) for x in input().split()]
a = []
for i in range(n):
	a.append(input())
dp = [[inf, inf] for i in range(n)]
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	dp[i][0] = min(dp[i - 1][0] if a[i] >= a[i - 1] else inf, dp[i - 1][1] if a[i] >= a[i - 1][::-1] else inf)
	dp[i][1] = min(dp[i - 1][0] + c[i] if a[i][::-1] >= a[i - 1] else inf, dp[i - 1][1] + c[i] if a[i][::-1] >= a[i - 1][::-1] else inf)
ans = min(dp[-1])
print(-1 if ans == inf else ans)


import math
n = int(input())
w = list(map(int, input().split()))
dp = []
s = []
fail = False
for x in range(n):
	s.append(input())
	dp.append([math.inf, math.inf])
	if x == 0:
		dp[x][0] = 0
		dp[x][1] = w[x]
	else:
		if s[x] >= s[x - 1]:
			dp[x][0] = min(dp[x - 1][0], dp[x][0])
		if s[x] >= s[x - 1][::-1]:
			dp[x][0] = min(dp[x - 1][1], dp[x][0])
		if s[x][::-1] >= s[x - 1]:
			dp[x][1] = min(dp[x - 1][0] + w[x], dp[x][1])
		if s[x][::-1] >= s[x - 1][::-1]:
			dp[x][1] = min(dp[x - 1][1] + w[x], dp[x][1])
	if dp[x][0] == math.inf and dp[x][1] == math.inf:
		fail = True
		break
if fail:
	print(-1)
else:
	print(min(dp[n - 1][0], dp[n - 1][1]))


def update(n, m):
	if n == -1:
		return m
	if m == -1:
		return n
	return min(n, m)
n = int(input())
costs = list(map(int, input().split()))
strs = [input() for x in range(n)]
res = [[-1] * n, [-1] * n]
res[0][0] = 0
res[1][0] = costs[0]
for i in range(1, n):
	if res[0][i - 1] > -1:
		if strs[i - 1] <= strs[i]:
			res[0][i] = update(res[0][i], res[0][i - 1])
		if strs[i - 1] <= strs[i][::-1]:
			res[1][i] = update(res[1][i], res[0][i - 1] + costs[i])
	if res[1][i - 1] > -1:
		if strs[i - 1][::-1] <= strs[i]:
			res[0][i] = update(res[0][i], res[1][i - 1])
		if strs[i - 1][::-1] <= strs[i][::-1]:
			res[1][i] = update(res[1][i], res[1][i - 1] + costs[i])
print(update(res[0][-1], res[1][-1]))


list_int_input = lambda inp: list(map(int, inp.split()))
int_input = lambda inp: int(inp)
string_to_list_input = lambda inp: list(inp)
n = int(input())
a = list_int_input(input())
i = 0
ps = ['', '']
pv = [0, 0]
ans = 10 ** 16
while i < n:
	sr = input()
	(x, y) = (ans, ans)
	if ps[0] <= sr:
		x = pv[0]
	if ps[1] <= sr:
		x = min(x, pv[1])
	ssr = sr[::-1]
	if ps[0] <= ssr:
		y = a[i] + pv[0]
	if ps[1] <= ssr:
		y = min(y, a[i] + pv[1])
	pv = [x, y]
	ps = [sr, ssr]
	i += 1
ans = min(pv)
if ans == 10 ** 16:
	print(-1)
else:
	print(ans)


n = int(input())
costs = [int(x) for x in input().split()]
a = [input() for x in range(n)]
r = [a[x][::-1] for x in range(len(a))]
dp = [[float('inf'), float('inf')] for x in range(n)]
dp[0][0] = 0
dp[0][1] = costs[0]
for x in range(1, len(a)):
	best = float('inf')
	if a[x] >= a[x - 1]:
		best = min(best, dp[x - 1][0])
	if a[x] >= r[x - 1]:
		best = min(best, dp[x - 1][1])
	dp[x][0] = best
	best = float('inf')
	if r[x] >= a[x - 1]:
		best = min(best, dp[x - 1][0] + costs[x])
	if r[x] >= r[x - 1]:
		best = min(best, dp[x - 1][1] + costs[x])
	dp[x][1] = best
ans = min(dp[-1])
if ans == float('inf'):
	print(-1)
else:
	print(ans)


n = int(input())
a = list(map(int, input().split()))
opt = [0] * (n + 5)
optr = [a[0]] + [0] * (n + 5)
Maxima = 999999999999999999999999999999
s = []
sr = []
for i in range(0, n):
	t = input()
	s.append(t)
	sr.append(t[::-1])
for i in range(1, n):
	if s[i] >= s[i - 1] and s[i] >= sr[i - 1]:
		opt[i] = min(opt[i - 1], optr[i - 1])
	elif s[i] >= s[i - 1]:
		opt[i] = opt[i - 1]
	elif s[i] >= sr[i - 1]:
		opt[i] = optr[i - 1]
	else:
		opt[i] = Maxima
	if sr[i] >= s[i - 1] and sr[i] >= sr[i - 1]:
		optr[i] = min(opt[i - 1], optr[i - 1]) + a[i]
	elif sr[i] >= s[i - 1]:
		optr[i] = opt[i - 1] + a[i]
	elif sr[i] >= sr[i - 1]:
		optr[i] = optr[i - 1] + a[i]
	else:
		optr[i] = Maxima
k = min(opt[n - 1], optr[n - 1])
if k == Maxima:
	print(-1)
else:
	print(k)


tc = 1
for _ in range(tc):
	n = int(input())
	A = list(map(int, input().split()))
	S = [input() for i in range(n)]
	dp = [[10 ** 20, 10 ** 20] for i in range(n)]
	dp[0][1] = A[0]
	dp[0][0] = 0
	for i in range(1, n):
		if S[i] >= S[i - 1]:
			dp[i][0] = dp[i - 1][0]
		if S[i] >= S[i - 1][::-1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if S[i][::-1] >= S[i - 1]:
			dp[i][1] = dp[i - 1][0] + A[i]
		if S[i][::-1] >= S[i - 1][::-1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + A[i])
	print(min(dp[-1]) if min(dp[-1]) < 10 ** 20 else -1)


n = int(input())
c = list(map(int, input().split()))
(l, s) = ([[10 ** 20, 10 ** 20] for i in range(n)], [])
for i in range(0, n):
	s.append(input())
l[0] = [0, c[0]]
for i in range(1, n):
	k = 0
	(r1, r2) = (s[i - 1][::-1], s[i][::-1])
	if s[i] >= s[i - 1]:
		l[i][0] = min(l[i][0], l[i - 1][0])
		k += 1
	if s[i] >= r1:
		l[i][0] = min(l[i][0], l[i - 1][1])
		k += 1
	if r2 >= s[i - 1]:
		l[i][1] = min(l[i][1], l[i - 1][0] + c[i])
		k += 1
	if r2 >= r1:
		l[i][1] = min(l[i][1], l[i - 1][1] + c[i])
		k += 1
	if k == 0:
		print(-1)
		exit()
ans = min(l[-1])
print(ans if ans < 10 ** 20 else -1)


n = int(input())
c = [int(s) for s in input().split(' ')]
C_rev = c[0]
C_nrev = 0
last_s = input()
last_s_rev = last_s[::-1]
for i in range(1, n):
	s = input()
	s_rev = s[::-1]
	new_C_nrev = float('inf')
	if last_s <= s:
		new_C_nrev = min(new_C_nrev, C_nrev)
	if last_s_rev <= s:
		new_C_nrev = min(new_C_nrev, C_rev)
	new_C_rev = float('inf')
	if last_s <= s_rev:
		new_C_rev = min(new_C_rev, C_nrev + c[i])
	if last_s_rev <= s_rev:
		new_C_rev = min(new_C_rev, C_rev + c[i])
	if min(C_rev, C_nrev) == float('inf'):
		break
	C_rev = new_C_rev
	C_nrev = new_C_nrev
	last_s = s
	last_s_rev = s_rev
print(-1 if min(C_rev, C_nrev) == float('inf') else min(C_rev, C_nrev))


def main():
	n = int(input())
	costs = list(map(int, input().split()))
	dp = []
	prev = ''
	for i in range(n):
		s = input()
		if not prev:
			dp.append([0, costs[0]])
		else:
			cost = [float('inf'), float('inf')]
			if s >= prev:
				cost[0] = min(cost[0], dp[-1][0])
			if s >= prev[::-1]:
				cost[0] = min(cost[0], dp[-1][1])
			if s[::-1] >= prev:
				cost[-1] = min(cost[-1], dp[-1][0] + costs[i])
			if s[::-1] >= prev[::-1]:
				cost[-1] = min(cost[-1], dp[-1][1] + costs[i])
			if s < prev and s < prev[::-1] and (s[::-1] < prev) and (s[::-1] < prev[::-1]):
				print(-1)
				return
			dp.append(cost)
		prev = s
	if min(dp[-1]) == float('inf'):
		print(-1)
		return
	print(min(dp[-1]))
main()


n = int(input())
C = tuple(map(int, input().split()))
A = tuple((input() for _ in range(n)))
B = tuple((A[i][::-1] for i in range(n)))
INF = 1 << 47
a = 0
b = C[0]
for i in range(1, n):
	c = INF if B[i] < A[i - 1] else C[i] + a
	if A[i] < A[i - 1]:
		a = INF
	if B[i - 1] <= A[i]:
		a = min(a, b)
	if B[i - 1] <= B[i]:
		c = min(c, C[i] + b)
	b = c
	if INF <= a and INF <= b:
		break
c = min(a, b)
print(c if INF > c else -1)


n = int(input())
arr = list(map(int, input().split()))
dp = [[0, 0] for i in range(n)]
dp[0][0] = arr[0]
dp[0][1] = 0
prev = input()
for i in range(1, n):
	bool1 = True
	bool2 = True
	curr = input()
	curr_rev = ''
	prev_rev = ''
	l1 = len(prev)
	l2 = len(curr)
	for j in range(l2):
		curr_rev += curr[l2 - j - 1]
	for j in range(l1):
		prev_rev += prev[l1 - 1 - j]
	if curr >= prev and curr >= prev_rev:
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][1])
	elif curr >= prev:
		dp[i][1] = dp[i - 1][1]
	elif curr >= prev_rev:
		dp[i][1] = dp[i - 1][0]
	else:
		dp[i][1] = 10 ** 14
		bool1 = False
	if curr_rev >= prev and curr_rev >= prev_rev:
		dp[i][0] = min(arr[i] + dp[i - 1][1], arr[i] + dp[i - 1][0])
	elif curr_rev >= prev:
		dp[i][0] = arr[i] + dp[i - 1][1]
	elif curr_rev >= prev_rev:
		dp[i][0] = arr[i] + dp[i - 1][0]
	else:
		dp[i][0] = 10 ** 14
		bool2 = False
	if not (bool1 or bool2):
		print(-1)
		break
	prev = curr
final = min(dp[n - 1][0], dp[n - 1][1])
if bool1 or bool2:
	if final == 10 ** 14:
		print(-1)
	else:
		print(final)


import sys
readline = sys.stdin.readline
N = int(readline())
C = list(map(int, readline().split()))
inf = 10 ** 20
dp1 = [inf] * N
dp2 = [inf] * N
dp1[0] = 0
dp2[0] = C[0]
Ss = [readline().strip() for _ in range(N)]
pre = Ss[0]
rev = Ss[0][::-1]
ans = -1
for i in range(1, N):
	s = Ss[i]
	sr = s[::-1]
	if s >= pre:
		dp1[i] = min(dp1[i], dp1[i - 1])
	if s >= rev:
		dp1[i] = min(dp1[i], dp2[i - 1])
	if sr >= pre:
		dp2[i] = min(dp2[i], C[i] + dp1[i - 1])
	if sr >= rev:
		dp2[i] = min(dp2[i], C[i] + dp2[i - 1])
	if dp1[i] == dp2[i] == inf:
		break
	pre = s[:]
	rev = sr[:]
else:
	ans = min(dp1[N - 1], dp2[N - 1])
print(ans)


n = int(input())
c = list(map(int, input().split()))
s = []
d = []
for i in range(n):
	k = input()
	s.append(k)
	k = k[::-1]
	d.append(k)
op = [[-1 for i in range(2)] for x in range(n)]
op[0][1] = c[0]
op[0][0] = 0
for i in range(1, n):
	if s[i] >= s[i - 1]:
		if op[i - 1][0] != -1:
			if op[i][0] == -1:
				op[i][0] = op[i - 1][0]
			else:
				op[i][0] = min(op[i][0], op[i - 1][0])
	if s[i] >= d[i - 1]:
		if op[i - 1][1] != -1:
			if op[i][0] == -1:
				op[i][0] = op[i - 1][1]
			else:
				op[i][0] = min(op[i][0], op[i - 1][1])
	if d[i] >= d[i - 1]:
		if op[i - 1][1] != -1:
			if op[i][1] == -1:
				op[i][1] = op[i - 1][1] + c[i]
			else:
				op[i][1] = min(op[i][1], op[i - 1][1] + c[i])
	if d[i] >= s[i - 1]:
		if op[i - 1][0] != -1:
			if op[i][1] == -1:
				op[i][1] = op[i - 1][0] + c[i]
			else:
				op[i][1] = min(op[i][1], op[i - 1][0] + c[i])
if op[n - 1][1] == -1:
	print(op[n - 1][0])
elif op[n - 1][0] == -1:
	print(op[n - 1][1])
else:
	print(min(op[n - 1][0], op[n - 1][1]))


import os, sys
from io import BytesIO, IOBase
from math import inf, isinf

def main():
	n = int(input())
	c = list(map(int, input().split()))
	st = [input().strip() for _ in range(n)]
	r = [i[::-1] for i in st]
	dp = [[inf, inf] for _ in range(n)]
	dp[0] = [0, c[0]]
	for i in range(1, n):
		if st[i] >= st[i - 1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if st[i] >= r[i - 1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if r[i] >= st[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + c[i])
		if r[i] >= r[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + c[i])
	print(-1 if isinf(min(dp[-1])) else min(dp[-1]))
main()


from sys import maxsize, stdin
n = int(input())
ls = list(map(int, input().split()))
ar = []
for i in range(n):
	ar.append(input())
dp = [[100000000000000000000000000000000, 100000000000000000000000000000000] for i in range(n)]
dp[0][0] = 0
dp[0][1] = ls[0]
for i in range(1, n):
	if ar[i] >= ar[i - 1]:
		dp[i][0] = min(dp[i - 1][0], dp[i][0])
	if ar[i] >= ar[i - 1][::-1]:
		dp[i][0] = min(dp[i - 1][1], dp[i][0])
	if ar[i][::-1] >= ar[i - 1]:
		dp[i][1] = min(dp[i - 1][0] + ls[i], dp[i][1])
	if ar[i][::-1] >= ar[i - 1][::-1]:
		dp[i][1] = min(dp[i - 1][1] + ls[i], dp[i][1])
ans = min(dp[n - 1])
if ans == 100000000000000000000000000000000:
	print(-1)
else:
	print(ans)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from heapq import *
from math import gcd, factorial, floor, ceil
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 10 ** 9 + 7

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
dp = [[-1, -1] for i in range(100005)]
inf = 10 ** 18

@iterative
def rec(s, c, pos, flag):
	if pos == len(s):
		yield 0
	if dp[pos][1 if flag else 0] != -1:
		yield dp[pos][1 if flag else 0]
	temp = 10 ** 18
	if flag:
		if s[pos] >= s[pos - 1][::-1]:
			temp = min(temp, (yield rec(s, c, pos + 1, False)))
		if s[pos][::-1] >= s[pos - 1][::-1]:
			temp = min(temp, c[pos] + (yield rec(s, c, pos + 1, True)))
	else:
		if s[pos] >= s[pos - 1]:
			temp = min(temp, (yield rec(s, c, pos + 1, False)))
		if s[pos][::-1] >= s[pos - 1]:
			temp = min(temp, c[pos] + (yield rec(s, c, pos + 1, True)))
	dp[pos][1 if flag else 0] = temp
	yield temp

def solve(case):
	n = int(inp())
	c = lis()
	s = []
	for i in range(n):
		s.append(inp())
	for i in range(1, n):
		if s[i] > s[i - 1] or s[i] > s[i - 1][::-1]:
			continue
		new = s[i][::-1]
		if new >= s[i - 1] or new >= s[i - 1][::-1]:
			continue
		print(-1)
		return
	(dp[0][0], dp[0][1]) = (0, c[0])
	temp = min(c[0] + rec(s, c, 1, True), rec(s, c, 1, False))
	if temp > 10 ** 15:
		print(-1)
		return
	print(temp)
testcase(1)


def cmp(a, b, c):
	if b == -1:
		return a
	if a == -1 or b + c < a:
		return b + c
	return a
n = int(input())
cs = list(map(int, input().split()))
dp = [[-1, -1] for i in range(n)]
dp[0][0] = 0
dp[0][1] = cs[0]
last = input()
for i in range(1, n):
	s = input()
	rlast = last[::-1]
	rs = s[::-1]
	if s >= last:
		dp[i][0] = cmp(dp[i][0], dp[i - 1][0], 0)
	if s >= rlast:
		dp[i][0] = cmp(dp[i][0], dp[i - 1][1], 0)
	if rs >= last:
		dp[i][1] = cmp(dp[i][1], dp[i - 1][0], cs[i])
	if rs >= rlast:
		dp[i][1] = cmp(dp[i][1], dp[i - 1][1], cs[i])
	last = s
if dp[n - 1][0] == -1:
	print(dp[n - 1][1])
elif dp[n - 1][1] == -1:
	print(dp[n - 1][0])
else:
	print(min(dp[n - 1][0], dp[n - 1][1]))


from sys import stdin
INF = float('infinity')
test = list(map(str.strip, stdin.readlines()))
n = int(test[0])
energy = [int(c) for c in test[1].split()]
dp = [[INF] * 2 for _ in range(n)]
dp[0][0] = 0
dp[0][1] = energy[0]
prev = test[2]
prev_rev = test[2][::-1]
for i in range(1, n):
	line = test[i + 2]
	line_rev = line[::-1]
	no_reversed = INF
	if line >= prev and dp[i - 1][0] != INF:
		no_reversed = dp[i - 1][0]
	if line >= prev_rev and dp[i - 1][1] != INF:
		no_reversed = min(no_reversed, dp[i - 1][1])
	dp[i][0] = no_reversed
	reverse = INF
	if line_rev >= prev and dp[i - 1][0] != INF:
		reverse = dp[i - 1][0] + energy[i]
	if line_rev >= prev_rev and dp[i - 1][1] != INF:
		reverse = min(reverse, dp[i - 1][1] + energy[i])
	dp[i][1] = reverse
	prev = line
	prev_rev = line_rev
ans = min(dp[-1])
print(ans if ans != INF else -1)


n = int(input())
c = [int(i) for i in input().split()]
a = [input() for i in range(n)]
inf = [[10 ** 15, 10 ** 15] for i in range(n)]
inf[0][0] = 0
inf[0][1] = c[0]

def howMany(i):
	inf[i][0] = min(inf[i - 1][0] if a[i] >= a[i - 1] else 10 ** 15, inf[i - 1][1] if a[i] >= a[i - 1][::-1] else 10 ** 15)
	inf[i][1] = min(inf[i - 1][0] + c[i] if a[i][::-1] >= a[i - 1] else 10 ** 15, inf[i - 1][1] + c[i] if a[i][::-1] >= a[i - 1][::-1] else 10 ** 15)
for j in range(1, n):
	howMany(j)
ans = min(inf[n - 1][0], inf[n - 1][1])
if ans >= 10 ** 15:
	print(-1)
else:
	print(ans)


INF = 10 ** 30
n = int(input())
c = list(map(int, input().split()))
s = [input().strip() for _ in range(n)]
rev_s = [el[::-1] for el in s]
res = [[INF, INF] for _ in range(n)]
res[0][1] = c[0]
res[0][0] = 0
for idx in range(1, n):
	if s[idx] >= s[idx - 1]:
		res[idx][0] = res[idx - 1][0]
	if s[idx] >= rev_s[idx - 1]:
		res[idx][0] = min(res[idx][0], res[idx - 1][1])
	if rev_s[idx] >= s[idx - 1]:
		res[idx][1] = res[idx - 1][0] + c[idx]
	if rev_s[idx] >= rev_s[idx - 1]:
		res[idx][1] = min(res[idx][1], res[idx - 1][1] + c[idx])
	if res[idx] == [INF, INF]:
		break
res = min(*res[-1])
print(-1 if res == INF else res)


n = int(input())
e = [int(t) for t in input().split(' ')]
a = [[0, 0] for _ in range(n)]
s = input()
rs = s[::-1]
MAX = 10 ** 9 * 100000 + 1
a[0][0] = 0
a[0][1] = e[0]
a[-1][0] = a[-1][1] = MAX

def compare(a, b):
	if a < b:
		return -1
	if a > b:
		return 1
	return 0
for i in range(1, n):
	ns = input()
	rns = ns[::-1]
	comp = compare(s, ns)
	always_less = True
	if ns >= s or ns >= rs:
		always_less = False
		if ns >= s and ns >= rs:
			a[i][0] = min(*a[i - 1])
		elif ns >= s:
			a[i][0] = a[i - 1][0]
		else:
			a[i][0] = a[i - 1][1]
	else:
		a[i][0] = MAX
	if rns >= s or rns >= rs:
		always_less = False
		if rns >= s and rns >= rs:
			a[i][1] = min(*a[i - 1]) + e[i]
		elif rns >= s:
			a[i][1] = a[i - 1][0] + e[i]
		else:
			a[i][1] = a[i - 1][1] + e[i]
	else:
		a[i][1] = MAX
	if always_less:
		break
	(s, rs) = (ns, rns)
ans = min(*a[-1])
if ans >= MAX:
	print(-1)
else:
	print(ans)


n = int(input())
c = list(map(int, input().split()))
(a, b) = (0, 0)
last = ''
for i in range(n):
	x = input()
	if i == 0:
		a = 0
		b = c[i]
	else:
		(aa, bb) = (10 ** 15, 10 ** 15)
		if x >= last:
			aa = min(aa, a)
		if x >= last[::-1]:
			aa = min(aa, b)
		if x[::-1] >= last:
			bb = min(bb, a + c[i])
		if x[::-1] >= last[::-1]:
			bb = min(bb, b + c[i])
		(a, b) = (aa, bb)
	last = x
if min(a, b) > sum(c):
	print(-1)
else:
	print(min(a, b))


N = int(input())
cost = list(map(int, input().split()))
dpn = [float('inf') for i in range(N)]
dpr = [float('inf') for i in range(N)]
string = [input() for _ in range(N)]
dpn[0] = 0
dpr[0] = cost[0]
for i in range(1, N):
	s = string[i]
	rev_s = s[::-1]
	if string[i - 1] <= s:
		dpn[i] = min(dpn[i], dpn[i - 1])
	if string[i - 1][::-1] <= s:
		dpn[i] = min(dpn[i], dpr[i - 1])
	if string[i - 1] <= rev_s:
		dpr[i] = min(dpr[i], dpn[i - 1] + cost[i])
	if string[i - 1][::-1] <= rev_s:
		dpr[i] = min(dpr[i], dpr[i - 1] + cost[i])
ans = 0
K = min(dpr[N - 1], dpn[N - 1])
if K == float('inf'):
	print(-1)
else:
	print(K)


n = int(input())
c = input().split()
ls = []
for i in range(n):
	s = input()
	ls.append(s)
dp = [[10 ** 18, 10 ** 18] for i in range(n)]
flag = True
for i in range(n):
	if i == 0:
		dp[i][0] = 0
		dp[i][1] = int(c[i])
	else:
		if ls[i] >= ls[i - 1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][0])
		if ls[i] >= ls[i - 1][::-1]:
			dp[i][0] = min(dp[i][0], dp[i - 1][1])
		if ls[i][::-1] >= ls[i - 1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][0] + int(c[i]))
		if ls[i][::-1] >= ls[i - 1][::-1]:
			dp[i][1] = min(dp[i][1], dp[i - 1][1] + int(c[i]))
if min(dp[n - 1][0], dp[n - 1][1]) == 10 ** 18:
	print(-1)
else:
	print(min(dp[n - 1][0], dp[n - 1][1]))


def get_cost(cur_s, last_s, forward, reverse, cur_cost):
	cost = None
	if forward is not None and cur_s >= last_s:
		cost = forward + cur_cost
	if reverse is not None and (cost is None or reverse + cur_cost < cost) and (cur_s >= last_s[::-1]):
		cost = reverse + cur_cost
	return cost
(n, c) = (int(input()), list(map(int, input().split())))
last_s = input()
(forward, reverse) = (0, c[0])
for i in range(1, n):
	cur_s = input()
	t = get_cost(cur_s, last_s, forward, reverse, 0)
	reverse = get_cost(cur_s[::-1], last_s, forward, reverse, c[i])
	forward = t
	last_s = cur_s
if forward is None and reverse is None:
	print(-1)
elif forward is None:
	print(reverse)
elif reverse is None:
	print(forward)
else:
	print(min(reverse, forward))


nax = 100000000000000.0 + 5
n = int(input())
(*c,) = map(int, input().split())
dp = [[0, c[0]]]
a = [input()]
for i in range(1, n):
	s = input()
	tmp = [nax, nax]
	for j in range(2):
		if s[::1 - 2 * j] >= a[-1]:
			tmp[j] = min(tmp[j], dp[-1][0] + c[i] * j)
		if s[::1 - 2 * j] >= a[-1][::-1]:
			tmp[j] = min(tmp[j], dp[-1][1] + c[i] * j)
	if tmp == [nax, nax]:
		exit(print(-1))
	dp.append(tmp)
	a.append(s)
print(min(dp[n - 1]))


n = int(input())
costs = list(map(int, input().split()))
words = []
for _ in range(n):
	words.append(input())
(cost, costInv) = (0, costs[0])
for i in range(1, n):
	(newCost, newCostInv) = (float('inf'), float('inf'))
	if words[i] >= words[i - 1]:
		newCost = min(newCost, cost)
	if words[i] >= words[i - 1][::-1]:
		newCost = min(newCost, costInv)
	if words[i][::-1] >= words[i - 1]:
		newCostInv = min(newCostInv, cost + costs[i])
	if words[i][::-1] >= words[i - 1][::-1]:
		newCostInv = min(newCostInv, costInv + costs[i])
	cost = newCost
	costInv = newCostInv
	if min(cost, costInv) == float('inf'):
		print(-1)
		break
if min(cost, costInv) < float('inf'):
	print(min(cost, costInv))


n = int(input())
c = list(map(int, input().split()))
a = []
a.append([input() for _ in range(n)])
a.append([e[::-1] for e in a[0]])
inf = 1 << 60
dp = [[inf for _ in range(2)] for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
	for j in range(2):
		for k in range(2):
			if i == 1 or a[j][i - 1] >= a[k][i - 2]:
				dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * c[i - 1])
answer = min(dp[n])
if answer == inf:
	answer = -1
print(answer)


n = int(input())
C = [int(i) for i in input().split()]
inf = sum(C) * 2
ans = inf
(a, b) = (0, C[0])
prev = input()
rprev = prev[::-1]
for i in range(1, n):
	cur = input()
	rcur = cur[::-1]
	(p, q, r, s) = (inf, inf, inf, inf)
	if prev <= cur:
		p = a
	if prev <= rcur:
		q = a + C[i]
	if rprev <= cur:
		r = b
	if rprev <= rcur:
		s = b + C[i]
	a = min(p, r)
	b = min(q, s)
	prev = cur
	rprev = rcur
ans = min(a, b)
if ans == inf:
	print(-1)
else:
	print(ans)


n = int(input())
c = [int(x) for x in input().split()]
dp = [[10 ** 20, 10 ** 20] for i in range(n)]
arr = []
prev = input()
dp[0][0] = 0
dp[0][1] = c[0]
for i in range(1, n):
	s = input()
	if s >= prev:
		dp[i][0] = min(dp[i][0], dp[i - 1][0])
	if s[::-1] >= prev:
		dp[i][1] = min(dp[i][1], c[i] + dp[i - 1][0])
	if s >= prev[::-1]:
		dp[i][0] = min(dp[i][0], dp[i - 1][1])
	if s[::-1] >= prev[::-1]:
		dp[i][1] = min(dp[i][1], c[i] + dp[i - 1][1])
	prev = s
if min(dp[n - 1][0], dp[n - 1][1]) >= 10 ** 20:
	print(-1)
else:
	print(min(dp[n - 1][0], dp[n - 1][1]))


arg = int(input())
list1 = list(map(int, input().strip().split()))
dp = [[9999999999999999 for n in range(0, 2)] for r in range(0, arg)]
dp[0][0] = 0
dp[0][1] = list1[0]
strings = []
for a in range(1, arg + 1):
	strings_temp = input().strip()
	strings.append(strings_temp)
flag9 = 0
for i in range(1, arg):
	r = strings[i - 1][::-1]
	if strings[i] >= strings[i - 1] and strings[i] >= r:
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1])
	elif strings[i] >= strings[i - 1]:
		dp[i][0] = dp[i - 1][0]
	elif strings[i] >= r:
		dp[i][0] = dp[i - 1][1]
	r5 = strings[i][::-1]
	if r5 >= r and r5 >= strings[i - 1]:
		dp[i][1] = min(dp[i - 1][0] + list1[i], dp[i - 1][1] + list1[i])
	elif r5 >= r:
		dp[i][1] = dp[i - 1][1] + list1[i]
	elif r5 >= strings[i - 1]:
		dp[i][1] = dp[i - 1][0] + list1[i]
if min(dp[arg - 1][0], dp[arg - 1][1]) != 9999999999999999:
	print(min(dp[arg - 1][0], dp[arg - 1][1]))
else:
	print(-1)