불 끄기

집에 전구가 L개 일렬로 놓여 있고, 각 전구마다 상태를 바꾸는 스위치가 하나씩 달려 있다. 켜져 있는 전구의 스위치를 누르면 꺼지고, 꺼져 있는 전구의 스위치를 누르면 켜진다.

여러 스위치를 한 번에 누를 수 있는 장치가 있다. 이 장치에는 슬롯이 T개 일렬로 놓여 있으며, 각 슬롯에는 스위치를 누르는 막대가 꽂혀 있거나 비어 있다. 막대가 꽂힌 슬롯은 1, 비어 있는 슬롯은 0으로 나타낸다. 예를 들어 슬롯이 4개이고 첫째·둘째·넷째 슬롯에만 막대가 꽂혀 있으면 이 장치는 1101로 표기한다.

장치의 가장 왼쪽 슬롯을 i번 스위치에 맞추어 한 번 누르면, 막대가 꽂힌 슬롯에 대응하는 스위치만 눌린다. 즉 j번째 슬롯(1 ≤ j ≤ T)에 막대가 있으면 i+j−1번 전구의 상태가 바뀌고, 비어 있으면 그 전구는 그대로다. 장치의 T개 슬롯은 모두 어떤 스위치에 대응되어야 하므로 슬롯이 전구 범위를 벗어나면 안 되고, 장치를 회전할 수도 없다. 따라서 가장 왼쪽 슬롯은 1번부터 L−T+1번 스위치까지에만 맞출 수 있다.

장치는 원하는 위치에서 원하는 횟수만큼 누를 수 있으며, 한 번도 누르지 않아도 된다. 전구의 처음 상태와 장치의 슬롯 상태가 주어질 때, 켜져 있는 전구의 개수를 가장 작게 만들었을 때의 그 최솟값을 구하여라.

첫째 줄에 L (3 ≤ L ≤ 50)과 T (1 ≤ T ≤ 7)가 공백으로 구분되어 주어진다.

둘째 줄에 길이가 L인 문자열이 주어진다. i번째 문자가 1이면 i번 전구가 켜진 상태, 0이면 꺼진 상태이다.

셋째 줄에 길이가 T인 문자열이 주어진다. 1은 막대가 꽂힌 슬롯, 0은 빈 슬롯을 뜻한다.

장치를 여러 번(0번 포함) 사용해서 만들 수 있는 켜진 전구 개수의 최솟값을 정수 하나로 출력한다.

L = 10, T = 4, 장치가 1101이고 모든 전구가 켜져 있는 경우를 생각하자. 예를 들어 다음 순서로 장치를 누르면 (각 줄은 누른 뒤의 전구 상태):

• 1111111111 — 처음 상태
• 1100101111 — 3번 스위치에 맞추어 누른 뒤
• 0001101111 — 1번 스위치에 맞추어 누른 뒤
• 0000000111 — 4번 스위치에 맞추어 누른 뒤
• 0000001010 — 7번 스위치에 맞추어 누른 뒤
• 0000010000 — 6번 스위치에 맞추어 누른 뒤

와 같이 켜진 전구를 1개까지 줄일 수 있고, 이보다 더 줄일 수는 없다. 따라서 이 경우의 답은 1이다.