You are given two binary strings s1 and s2 of length n, and an integer x.

You can apply any of the following two operations on s1 any number of times:

• Select two distinct indices i and j such that $0 \leq i < j < n$, and invert the characters at s1[i] and s1[j]. This operation costs x.

• Select an index i such that $0 \leq i < n - 1$, and invert the characters at both s1[i] and s1[i + 1]. This operation costs $1$.

Return the minimum total cost needed to make s1 identical to s2, or $-1$ if it is impossible to make them equal.

Note: Inverting a character changes $'0'$ to $'1'$ and $'1'$ to $'0'$.

Constraints:

• n $=$ s1.length $=$ s2.length

• $1 \leq$ n, x $\leq 500$

• s1 and s2 consist only of the characters $'0'$ and $'1'$.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.