Codeforces Round #821 (Div. 2)

D2. Zero-One (Hard Version)

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

This is the hard version of this problem. In this version, n≤5000 holds, and this version has no restriction between x and y. You can make hacks only if both versions of the problem are solved.

You are given two binary strings aa and bb, both of length nn. You can do the following operation any number of times (possibly zero).

• Select two indices ll and rr (l
• Change alal to (1−al) and arar to (1−ar).
• If l+1=r, the cost of the operation is x. Otherwise, the cost is y.

You have to find the minimum cost needed to make aa equal to bb or say there is no way to do so.

Input

The first line contains one integer tt (1≤t≤1000) — the number of test cases.

Each test case consists of three lines. The first line of each test case contains three integers nn, xx, and yy (5≤n≤5000, 1≤x,y≤10^9) — the length of the strings, and the costs per operation.

The second line of each test case contains the string aa of length nn. The string only consists of digits 0 and 1.

The third line of each test case contains the string bb of length nn. The string only consists of digits 0 and 1.

It is guaranteed that the sum of nn over all test cases doesn't exceed 5000.

Output

For each test case, if there is no way to make a equal to b, print −1. Otherwise, print the minimum cost needed to make a equal to b.

Example

input

Copy

6

5 8 9

01001

00101

6 2 11

000001

100000

5 7 2

01000

11011

7 8 3

0111001

0100001

6 3 4

010001

101000

5 10 1

01100

01100

output

Copy

8
10
-1
6
7
0

Note

In the first test case, selecting indices 2 and 3 costs 8, which is the minimum.

In the second test case, we can perform the following operations.

• Select indices 1 and 2. It costs 2, and aa is 110001 now.
• Select indices 2 and 3. It costs 2, and aa is 101001 now.
• Select indices 3 and 4. It costs 2, and aa is 100101 now.
• Select indices 4 and 5. It costs 2, and aa is 100011 now.
• Select indices 5 and 6. It costs 2, and aa is 100000 now.

The total cost is 10

In the third test case, we cannot make aa equal to bb using any number of operations.

In the fourth test case, we can perform the following operations.

• Select indices 3 and 6. It costs 3, and aa is 0101011 now.
• Select indices 4 and 6. It costs 3, and aa is 0100001 now.

The total cost is 6.

In the fifth test case, we can perform the following operations.

• Select indices 1 and 6. It costs 4, and aa is 110000 now.
• Select indices 2 and 3. It costs 3, and aa is 101000 now.

The total cost is 7.

In the sixth test case, we don't have to perform any operation.

 dp:要么和我前一个没匹配的通过若干个x或一次y消
要么是前i-1个中剩下的直接用y消

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
typedef double db;
const int N=5010;
string s,t;
int dp[N];
int a[N];
int n,x,y,cnt,ans;
void solve()
{
    cin>>n>>x>>y>>s>>t;
    s=" "+s;
    t=" "+t;
    ans=cnt=0;
    int fg=0,st=0;
    for(int i=1; i<=n; i++)
    {
        if(s[i]!=t[i])
        {
            cnt++;
            st=i;
            a[cnt]=i;
        }
    }
    if(cnt%2)
    {
        cout<<-1<<"\n";
        return;
    }
    if(cnt==0)
    {
        cout<<0<<"\n";
        return;
    }
    if(x>=y)  //D1
    {
        if(cnt==2&&s[st-1]!=t[st-1])cout<<min(x,y*2)<<"\n";
        else cout<<cnt*y/2<<"\n";
        return;
    }
    for(int i=2; i<=cnt; i++)
    {
        if(i%2)
        {
            dp[i]=min(dp[i-2]+min((a[i]-a[i-1])*x,y),dp[i-1]);
        }
        else
        {
            dp[i]=min(dp[i-2]+min((a[i]-a[i-1])*x,y),dp[i-1]+y);
        }
    }
    cout<<dp[cnt]<<"\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}