Sắp xếp xâu bằng phép đảo

Cho $n$ xâu chỉ gồm các chữ cái latin in thường. Với mỗi xâu $i$, đảo ngược nó (chữ cái đầu thành cuối, thứ hai thành thứ áp cuối, ...) tốn $c_i$ đơn vị năng lượng.

Bạn không được phép đổi chỗ hai xâu bất kỳ — thao tác duy nhất là đảo ngược một xâu. Hãy tìm tổng năng lượng nhỏ nhất cần dùng để dãy $n$ xâu (theo thứ tự đã cho) được sắp xếp theo thứ tự từ điển không giảm, hoặc thông báo điều đó là không thể.

Xâu $A$ nhỏ hơn xâu $B$ theo thứ tự từ điển nếu $A$ là tiền tố thực sự của $B$ ($|A|<|B|$ và $A$ trùng với $|A|$ ký tự đầu của $B$), hoặc tại vị trí đầu tiên mà chúng khác nhau, ký tự của $A$ nhỏ hơn ký tự của $B$. Hai xâu bằng nhau đứng cạnh nhau không vi phạm điều kiện sắp xếp.

Dữ liệu vào

• Dòng đầu: số nguyên $n$ — số lượng xâu.
• Dòng thứ hai: $n$ số nguyên $c_1,c_2,\dots ,c_n$ — chi phí đảo ngược của từng xâu.
• $n$ dòng tiếp theo: dòng thứ $i$ chứa xâu thứ $i$, gồm các chữ cái latin in thường.

Dữ liệu ra

In ra tổng năng lượng nhỏ nhất cần dùng, hoặc $-1$ nếu không thể.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le c_i\le {10}^9$
• Tổng độ dài các xâu không vượt quá ${10}^5$.

Ví dụ