비트 문자열 재배열하기

비트 문자열은 0과 1로만 이루어진 문자열이다. 비트 문자열 하나를 받아서 정해진 문자열로 바꾸어야 한다. 이때 할 수 있는 연산은 인접한 두 비트를 서로 바꾸는 것 하나뿐이다.

처음 문자열은 비트를 그대로 나열해서 주어진다. 반면 목표 문자열은 '연속 코드'로 주어진다. 연속 코드는 문자열에 나타나는 연속된 0 또는 1의 개수를 앞에서부터 차례대로 적은 수열이다. 예를 들어 "011100"의 연속 코드는 "1 3 2"이다. 연속 코드가 같은 문자열은 항상 두 개다. 0으로 시작하는 것 하나와 1로 시작하는 것 하나다.

처음 문자열을 목표 문자열로 바꾸는 데 필요한 최소 연산 횟수를 구하여라.

첫 줄에 두 정수 $N$ ($1 \le N \le 15$)과 $M$ ($1 \le M \le N$)이 주어진다. 둘째 줄에 처음 문자열을 이루는 $N$개의 비트가 공백으로 구분되어 주어진다. 셋째 줄에 목표 문자열의 연속 코드가 $M$개의 정수로 차례대로 주어진다.

연속 코드의 각 수는 1 이상이고, 모두 더하면 $N$이 된다. 주어진 비트 문자열을 연속 코드가 나타내는 문자열로 항상 바꿀 수 있음이 보장된다.

필요한 최소 연산 횟수를 출력한다.

비트 문자열 "100101"을 연속 코드가 "1 3 2"인 문자열로 바꾸는 경우를 보자. 목표가 될 수 있는 문자열은 "011100"과 "100011" 두 개다. "011100"으로 바꾸려면 연산이 4번 필요하지만, "100011"로 바꾸려면 1번이면 충분하다. 따라서 답은 1이다.