Felipe has a binary string A of length n (1 ≤ n ≤ 5000) which he wants to transform into string B (of length n as well) using a series of operations. He can use the following operations:
- Operation 1: He can move the last element of A to the front. For example, 01001 would become 10100.
- Operation 2: He can take any two consecutive elements and flip them. A flip turns a 1 into a 0 and a 0 into a 1. For example, if he applies this operation to the first two elements of 10100, it would become 01100.
Felipe actually doesn't like operation 2, so he wants to use it as few times as possible. Given A and B find the minimum number of operations type 2 needed to transform A into B, or say if it's impossible.
Input consist of two lines with binary strings A and B, respectively.
It is guaranteed that both strings have the same length.
Print one single line with the minimum number of operations type 2 needed to transform A into B. or - 1 if it's impossible to do so.
01001
01010
0
11111
00000
-1
001010
100001
1
Name |
---|