GA_similarity에서 NIA 서버에 자신의 스마트폰 기록을 남긴 것을 알게 된 승현이는 알리바이를 만들기 위해 친구들과 추후 연주회를 열기로 하고, 관리자에게는 “친구들과 같이 연습했다"고 말해 범행을 들키지 않게 하려고 합니다.

연주회에서 그가 연주할 악기는 자신이 대나무를 길게 깎아 만든 이름 없는 목관악기입니다. 이 악기에는 S개의 구멍이 있으며, 승현이는 1부터 N까지의 번호가 붙은 N개의 음을 구멍을 막고 부는 방식으로 연주해야 합니다. 각 구멍은 0부터 9까지의 번호가 붙은 10개의 방법으로 막을 수 있습니다.

모든 음은 모든 구멍을 정확히 하나의 방법으로 막아야만 연주할 수 있습니다. 각 방법은 수열로 정의되어 있으며, 이 수열은 음을 연주하기 위해 각 구멍을 막아야 하는 상태의 번호들로 이루어져 있습니다. 만약 구멍이 하나라도 제대로 막혀 있지 않으면, 이 악기가 모두가 불쾌해 하는(?) 소리를 내기 때문에, 승현이는 구멍을 몇 개 제대로 막지 않기보다는 아예 다른 음을 연주해야만 합니다.

이 악기를 연주할 밴드는 승현이에게 N개의 음으로 이루어진 곡을 쓴 악보를 주었는데, 이를 본 승현이는 경악하고 맙니다. 이 곡은 박자가 매우 빠르고 음이 복잡하여 연주가 까다로웠습니다. 그래서 안타깝게도, 승현이는 손가락의 속도가 G이기 때문에 이 곡을 완벽히 연주할 수가 없습니다. (곡을 잘 받으면 완벽히 연주할 수도..) 그가 2개의 연속적인 음을 완벽히 연주하기 위해서는, G개 이하의 구멍을 막는 상태만을 바꿔야 합니다.

이러한 이유로 그는 가끔 N개의 음에 속하는 틀린 음을 연주하기로 했습니다. 각각의 틀린 음을 연주하는 것을 “실수"라고 정의해 봅시다. NIA 서버 관리자가 연주회에 와서 연습을 했는지 하지 않았는지 판단하여 시비를 걸 수도 있기 때문에, 승현이는 실수를 최소화해야만 합니다.

밴드가 승현이에게 넘긴 악보가 주어질 때, 승현이가 이 곡을 연주할 때 실수하는 최소 횟수를 구하는 프로그램을 작성하세요.

입력

• 첫째 줄에 이 목관 악기가 낼 수 있는 음의 수 N(1≤N≤100)과 구멍의 수 S, 손가락의 속도 G(0≤G<S≤100)가 공백을 사이로 두고 주어집니다.
• 다음 N개 줄에 각 음을 연주하기 위해 구멍을 막는 상태를 나타낸 수열들이 한 줄에 하나씩 주어집니다. 이 수열은 공백 없이 주어지며, 위에서 i+1번째 줄의 왼쪽에서 j번째 숫자는 i번 음을 연주하기 위해 j번 구멍을 막아야 할 상태를 의미합니다. 구멍은 0부터 9까지의 번호가 붙은 10개의 상태로 막을 수 있습니다.
• N+2번째 줄에 밴드가 준 곡에 나오는 음표들의 수 L(1≤L≤100,000)가 주어집니다. 마지막 줄에는 곡에 나온 음표 L개의 음이 공백을 사이로 두고 차례대로 주어집니다. (주어진 멜로디대로 연주하면 실수 없이 연주를 완벽하게 마칠 수 있습니다.)

출력

첫째 줄에 승현이가 곡을 연주할 때 실수하는 최소 횟수를 출력합니다.

입출력 예

입력

5 4 2
1111
2101
2000
0100
0000
7
1 5 4 5 3 2 1

출력

1

입출력 보충

위의 예제에서는 1 2 4 5 3 2 1 순서대로 연주하면 두 번째 음을 제외한 모든 음을 완벽하게 연주할 수 있습니다. 다른 어떤 경우에도 전혀 실수를 하지 않고서 모든 음을 연주하는 방법은 존재하지 않습니다.

출처:GENIUSainta.com