Shinchan wants to attend the Infotsav Tech-Fest of ABV-IIITM with his M friends. There is a queue at the entrance of the collage campus. Security Guards only allow their friends to enter if their names are lexicographically sorted i.e. Name[1] < Name[2] < Name[3] ...... < Name[M].

Magic Operation : Pick a name and reverse it .

You can perform this magic operation any number of times . you can reverse 0 to all M names but to reverse a Name[K] will require Cost[K].

Can you help Shinchan to sort his friends names with least minimum total cost.

Input :

First line contains an integer 1 <= M <=250000 : Number of friends.

Second line contains space separated M integer specifying the cost of reverse respective name.

Then M lines specifying the names. Total Numbers of characters are not greater then 500000

Output : Print least minimum total cost to sort names or -1 if not possible.