17375번 - 컨테이너 스페셜 저지

"크리컨테이너제작소"에서는 컨테이너를 제작해 파는데, 1톤짜리 컨테이너와 2톤짜리 컨테이너의 두 가지 종류를 취급한다. 이번에 컨테이너를 대량 발주받아 총 N개의 컨테이너를 제작했고, 제작된 순서대로 창고에 일렬로 늘어놓았다.

창고는 먼저 제작된 컨테이너가 먼저 출고되기 쉬운 형태인데, 안타깝게도 컨테이너가 제작된 순서와 컨테이너가 출고되어야 하는 순서는 다를 수 있다. 그래서 늘어선 컨테이너를 재배열해 컨테이너가 출고되어야 하는 순서와 맞추려고 한다. 무게가 같은 컨테이너는 서로 구별할 수 없기 때문에, 무게의 순서를 맞추면 된다.

컨테이너의 재배열에는 기계의 힘을 빌린다. 기계는 인접한 위치에 있는 컨테이너를 여럿 선택해서 순서를 뒤집을 수 있는데, 크기 문제로 최대 세 개의 컨테이너만 선택할 수 있다. 예를 들어 선택된 컨테이너의 무게가 순서대로 [2,1]이라면 뒤집어서 [1,2]가, [2,1,1]이라면 뒤집어서 [1,1,2]가, [2,2,1]이라면 뒤집어서 [1,2,2]가 되는 식이고, 넷 이상의 컨테이너를 선택하여 뒤집을 수는 없다.

이렇게 기계를 사용하면 비용이 발생하고, 비용은 선택된 컨테이너의 무게의 합에 기계를 한 번 가동하는 데 드는 비용 C를 더한 만큼이다. 그러므로 [2,1]을 뒤집는 비용은 3+C, [1,1,2]을 뒤집는 비용은 4+C이다.

실제 예를 들어 보자. 컨테이너가 늘어선 순서대로 무게를 나열했을 때 [2,2,1,2,1,2,1]라고 하고, 출고되어야 하는 순서대로 무게를 나열하면 [1,2,1,2,1,2,2]라고 하자. 다음은 C=0일 때와 C=2일 때 각각의 최적의 재배열 방법이다. 선택한 컨테이너는 진하게 표시되어 있다.

둘의 방법을 서로 바꿔보면, 서로가 최적이 아니게 되는 것을 알 수 있다.

N, C, 컨테이너가 제작된 순서대로 무게를 나열한 것, 컨테이너가 출고되어야 하는 순서대로 무게를 나열한 것이 주어진다. 이때 총 비용이 최소화 되도록 기계를 사용하여 컨테이너를 재배열하는 방법을 구하는 프로그램을 작성하라.

첫 번째 줄에는 제작된 컨테이너의 수를 나타내는 정수 N(1 ≤ N ≤ 500)과 기계를 사용하는 데 드는 기본 비용을 나타내는 정수 C(0 ≤ C ≤ 1,000)가 공백 하나를 사이에 두고 주어진다.

두 번째 줄에는 1 또는 2로 이루어진 길이 N인 문자열이 주어진다. 이 문자열의 i번째 문자는 i 번째로 제작된 컨테이너의 무게를 뜻한다. 이 순서는 현재 컨테이너가 늘어서 있는 순서와도 같다.

세 번째 줄에는 1 또는 2로 이루어진 길이 N인 문자열이 주어진다. 이 문자열의 i번째 문자는 i 번째로 출고되어야 하는 컨테이너의 무게를 뜻한다. 이 순서대로 컨테이너가 늘어서 있도록 해야 한다.

주어진 두 문자열에서 등장하는 1의 개수는 서로 같음이 보장된다. 역시 2의 개수도 서로 같음이 보장된다.

첫 번째 줄에 기계를 사용한 횟수를 나타내는 정수 K 를 출력한다.

다음 K개의 줄에는 기계를 사용하는 순서대로 두 정수 i,j (1 ≤ i < j ≤ N, j - i ≤ 2)가 공백 하나를 사이에 두고 출력되어야 한다. 이는 기계로 i 번째에 있는 컨테이너에서 j 번째에 있는 컨테이너까지 선택하여 위치를 뒤집었음을 나타낸다.

기계를 사용하는 데 든 총 비용이 최소가 되어야 정답으로 인정된다.