시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 1024 MB 34 8 8 40.000%

문제

영원한 건 절대 없어

결국에 넌 변했지

이유도 없어 진심이 없어

사랑 같은 소리 따윈 집어 쳐

오늘밤은 삐딱하게

<삐딱하게>를 감명 깊게 들은 정훈이는 삐딱해졌다. 정훈이는 혼자서 N개의 동전을 뒤집는 놀이를 조용히 하고 있었다. 원하는 동전을 하나 뒤집는 방식까지 불만인 정훈이는 화가 나서 책상을 쳤다. 그랬더니 한 번에 K개의 연속된 동전 중에 하나를 제외하고 모두 뒤집어졌다.

놀란 정훈이는 몇 번 해보다가 삐딱한 마음으로 책상을 치면 지정한 연속된 K개의 동전에서 원하는 동전 하나를 제외한 모두를 뒤집는 능력을 발견했다. 신나서 책상을 두드리던 정훈이는 손이 아파 이 능력만을 이용하여 동전들을 현재 상태에서 원하는 상태로 만드는 능력의 최소 사용 횟수를 구하려고 한다.

최소 횟수를 구하려고 하니 또 불만이 생긴 정훈이를 도와 최소 횟수를 구하자.

입력

첫째 줄에 두 정수 동전의 개수 N (1 ≤ N ≤ 100)과 뒤집는 범위 K (1 ≤ K ≤ min(10, N))가 주어진다.

다음 줄에는 동전의 현재 상태가 주어진다. 0이 앞면, 1이 뒷면이다.

그다음 줄에는 원하는 동전의 상태가 주어진다.

출력

정훈이가 책상을 쳐서 동전을 뒤집는 최소 횟수를 출력한다.

불가능한 경우 -1을 출력한다.

예제 입력 1

5 2
0 0 0 0 0
1 1 1 0 0

예제 출력 1

3

예제 입력 2

5 5
1 0 1 1 1
0 1 0 1 1

예제 출력 2

-1

예제 입력 3

5 3
0 0 0 0 0
0 1 0 1 0

예제 출력 3

1