열차

다음과 같이 놓인 선로를 생각하자.

선로 I, II, III에는 차량을 세울 수 있다. 한 번의 이동으로 선로 I과 선로 III 사이, 선로 II와 선로 III 사이에서 차량을 옮길 수 있지만, 선로 I과 선로 II 사이에서 직접 옮길 수는 없다. 한 선로 위에서 차량끼리 서로 지나칠 수 없다. 맞닿은 차량 여러 대는 한 번의 이동으로 함께 움직일 수 있다. 위 그림의 상황에서 차량 G와 A는 한 번의 이동으로 선로 III에서 선로 I로 함께 옮길 수 있고, 그러면 선로 I의 차량 순서는 B, F, F, G, A가 된다. 반면 차량 A만 따로 선로 III에서 선로 I로 옮길 수는 없다. 그러려면 차량 G를 지나쳐야 하는데 이는 허용하지 않는다. 각 선로는 모든 차량을 세울 만큼 길다.

한 선로의 차량 순서는 선로 III과 이어지는 쪽에서 가장 먼 차량부터 적는다.

처음에 차량 여러 대가 선로 I에 놓여 있고 선로 II와 선로 III는 비어 있다. 선로 I과 선로 III 사이, 선로 II와 선로 III 사이로 차량을 옮겨서 원하는 차량 순서를 선로 II에 만들어야 한다. 선로 II에는 원하는 차량만 남고 다른 차량은 남지 않아야 한다. 프로그램이 답할 질문은 이것이다. 원하는 차량만 원하는 순서로 선로 II에 남기는 이동 횟수의 최솟값은 얼마인가? 맞닿은 차량 두 대 이상이 한 번에 함께 움직여도 이동 한 번으로 센다.

처음에 차량 A, B, C, D, E가 선로 I에 ABCDE 순서로 놓여 있다고 하자. 즉 차량 A가 가장 왼쪽에 있고 차량 E가 가장 오른쪽에서 선로 III에 가장 가깝다. 마지막에 선로 II에 DBC를 만들고 싶다고 하자. 이동 네 번이면 된다. 먼저 차량 D와 E를 함께 선로 I에서 선로 III으로 옮기고, 다음으로 차량 D를 선로 III에서 선로 II로 옮기고, 다음으로 차량 B와 C를 함께 선로 I에서 선로 III으로 옮기고, 마지막으로 차량 B와 C를 함께 선로 III에서 선로 II로 옮긴다. 그림 3이 이동 과정을 보여 준다. 따라서 답은 4다.

(a) 첫 번째 이동 전	(b) 첫 번째 이동 후
(c) 두 번째 이동 후	(d) 세 번째 이동 후
(e) 네 번째이자 마지막 이동 후

그림 3: 예시의 이동 과정.

입력은 세 줄이다. 첫째 줄에 공백 하나로 구분한 정수 두 개가 주어진다. 첫 번째 정수 $i$는 처음에 선로 I에 놓인 차량의 수이고, 두 번째 정수 $j$는 선로 II에 만들려는 차량의 수다.

둘째 줄에는 선로 I의 처음 차량 순서를 나타내는 대문자 $i$개가 주어진다. 셋째 줄에는 선로 II에 만들려는 차량 순서를 나타내는 대문자 $j$개가 주어진다.

둘째 줄의 문자는 모두 서로 다르고, 셋째 줄의 문자도 모두 서로 다르며, 셋째 줄의 문자는 모두 둘째 줄에 나온다. $0 < i < 7$, $0 < j < 7$이다.

원하는 차량만 원하는 순서로 선로 II에 남기는 최소 이동 횟수를 정수 하나로 출력한다.