405205: GYM101845 B Binary Strings

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Binary Stringstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input consist of two lines with binary strings A and B, respectively.

It is guaranteed that both strings have the same length.

Output

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.

ExamplesInput
01001
01010
Output
0
Input
11111
00000
Output
-1
Input
001010
100001
Output
1

加入题单

上一题 下一题 算法标签: