codeforces706C

Hard problem

 CodeForces - 706C 

现在有 n 个由小写字母组成的字符串。他想要让这些字符串按字典序排列，但是他不能交换任意两个字符串。他唯一能做的事是翻转字符串。

翻转第 i 个字符串需要花费 c_i 的能量。他想知道将所有字符串排序最少要多少能量。

两个相邻的字符串可以相等，不一定要严格递增。

Input

第一行包含一个整数 n (2 ≤ n ≤ 100 000) — 表示字符串的数量。

第二行包含 n 个整数 c_i (0 ≤ c_i ≤ 10⁹)，第 i 个整数等于翻转第 i 个字符串所需的能量。

之后 n 行，每行包含一个小写英文字母。总长度不到 100 000。

Output

如果不可能有序，输出  - 1。否则输出最小所需的能量。

Example

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

第二个样例中翻转字符串 2 或字符串 3。翻转字符串 3 所需能量更少。

第三个样例不合法，所以输出  - 1。

第四个样例不合法，所以输出  - 1。

sol：dp较为明显，因为i-2及之前的翻转是不影响当前的转移的，dp[i][0/1]表示在第i个字符串，当前是否翻转

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0'); return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005;
int n;
ll Cost[N],dp[N][2];
char S_Last[N],S_Now[N];
inline bool Judge(char *S1,char *S2)
{
    int i,n1=strlen(S1+1),n2=strlen(S2+1);
    for(i=1;i<=min(n1,n2);i++) if(S1[i]!=S2[i])
    {
        return S1[i]<S2[i];
    }
    return (n1<=n2)?1:0;
}
int main()
{
    int i,j;
    R(n);
    for(i=1;i<=n;i++) R(Cost[i]);
    scanf("%s",S_Last+1);
    memset(dp,63,sizeof dp);
    dp[1][0]=0;
    dp[1][1]=Cost[1];
    for(i=2;i<=n;i++)
    {
        scanf("%s",S_Now+1);
        if(Judge(S_Last,S_Now))
        {
            dp[i][0]=min(dp[i][0],dp[i-1][0]);
        }
        reverse(S_Last+1,S_Last+strlen(S_Last+1)+1);
        if(Judge(S_Last,S_Now))
        {
            dp[i][0]=min(dp[i][0],dp[i-1][1]);
        }
        reverse(S_Now+1,S_Now+strlen(S_Now+1)+1);
        if(Judge(S_Last,S_Now))
        {
            dp[i][1]=min(dp[i][1],dp[i-1][1]+Cost[i]);
        }
        reverse(S_Last+1,S_Last+strlen(S_Last+1)+1);
        if(Judge(S_Last,S_Now))
        {
            dp[i][1]=min(dp[i][1],dp[i-1][0]+Cost[i]);
        }
        reverse(S_Now+1,S_Now+strlen(S_Now+1)+1);
        memmove(S_Last,S_Now,sizeof S_Last);
    }
    if(min(dp[n][0],dp[n][1])>100000000000000) puts("-1");
    else Wl(min(dp[n][0],dp[n][1]));
    return 0;
}
/*
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
*/