문제

인하가 실험 장비를 만지다가 실수로 경보를 울렸고, 잠들어 있던 기계오리가 깨어나고 말았다! 경보음에 놀란 기계오리는 연구실을 뛰쳐나와 복도로 향했다.

인하는 기계오리를 무서워해서 연구실 밖으로 따라 나갈 수 없다. 대신 연구실 내부에서, 복도에 설치된 도망 방지 시스템을 원격으로 조작해 기계오리의 이동을 차단하려고 한다.

복도에는 도망 방지 시스템과 연동된 개의 자물쇠가 있으며, 각 자물쇠는 잠겨 있거나 열려 있다. 모든 자물쇠의 상태를 순서대로 나타낸 길이 의 이진 문자열을 자물쇠 상태라고 하자.

자물쇠 상태는 다음과 같이 표현된다.

• 문자열의 번째 문자가 1이면, 번째 자물쇠는 잠겨 있다.
• 문자열의 번째 문자가 0이면, 번째 자물쇠는 열려 있다.

초기 자물쇠 상태는 문자열 , 목표 자물쇠 상태는 문자열 로 주어진다.

도망 방지 시스템에는 번부터 번까지 번호가 매겨진 개의 버튼이 있다. 번 버튼에는 길이 의 이진 문자열 가 적혀 있다.

인하는 한 번에 하나의 버튼만 누를 수 있으며, 같은 버튼을 여러 번 누를 수도 있다. 인하가 번 버튼을 누르면, 모든 ()에 대해 다음이 동시에 일어난다.

• 의 번째 문자가 1이면, 번째 자물쇠의 상태를 바꾼다. 즉, 열려 있으면 잠그고, 잠겨 있으면 연다.
• 의 번째 문자가 0이면, 해당 자물쇠의 상태는 변하지 않는다.

시스템은 매우 예민하여, 자물쇠 상태가 와 정확히 일치하는 순간 복도 전체에 셔터가 내려온다. 이때 기계오리는 도망칠 수 없게 된다.

인하는 버튼을 가능한 한 적게 눌러 자물쇠 상태를 로 만들고 싶다. 인하를 도와, 자물쇠 상태를 로 만들 수 있는지 판단하고, 가능하다면 필요한 버튼 누름 횟수의 최솟값을 구하자.

입력

첫째 줄에 와 이 공백으로 구분되어 주어진다. ()

둘째 줄에 길이 의 이진 문자열 가 주어진다.

셋째 줄에 길이 의 이진 문자열 가 주어진다.

그다음 개의 줄 중 번째 줄에는 길이 의 이진 문자열 가 주어진다. ()

출력

자물쇠 상태를 로 만들 수 있다면 필요한 버튼 누름 횟수의 최솟값을 출력한다. 자물쇠 상태를 로 만들 수 없다면 -1을 출력한다.

노트

길이 의 이진 문자열이란 0과 1로만 이루어진 길이 의 문자열을 말한다.