Train

Consider the following arrangement of train tracks.

Tracks I, II, and III hold train cars. One movement takes cars between Track I and Track III, or between Track II and Track III, but never directly between Track I and Track II. Cars cannot pass each other on a track. Adjacent cars can move together in one movement. In the situation drawn above, the cars G and A can move together in one movement from Track III to Track I, after which the sequence of cars on Track I is B, F, F, G, A. The car A cannot move alone from Track III to Track I, because doing so means passing car G, which is not allowed. Each track is long enough to hold all cars.

The sequence of cars on a track is written starting from the car furthest from the junction with Track III.

Initially a sequence of cars sits on Track I, and Tracks II and III are empty. The goal is to move cars between Tracks I and III and between Tracks II and III so that a desired sequence of cars, and no other cars, sits on Track II. The question your program answers is: what is the smallest number of movements that leaves the desired sequence of cars, and no other cars, on Track II? When two or more adjacent cars move together in one go, that counts as one single movement.

Say the cars A, B, C, D and E start on Track I in the order ABCDE. Car A is furthest to the left, and car E is furthest to the right and closest to Track III. Say we want the sequence DBC on Track II at the end. Four movements achieve this. First move cars D and E together from Track I to Track III, then move car D from Track III to Track II, then move cars B and C together from Track I to Track III, and finally move cars B and C together from Track III to Track II. Figure 3 shows the sequence of movements. The answer is therefore the number 4.

(a) Before first movement	(b) After first movement
(c) After second movement	(d) After third movement
(e) After fourth and final movement

Figure 3: Movements for the example.

The input consists of three lines. The first line contains two integers separated by a blank character. The first integer $i$ is the initial number of cars on Track I, and the second integer $j$ is the number of desired cars on Track II.

The second line contains $i$ capital letters giving the initial sequence of cars on Track I. The third line contains $j$ capital letters giving the desired sequence of cars on Track II.

All letters on the second line are distinct, all letters on the third line are distinct, every letter on the third line also occurs on the second line, $0 < i < 7$ and $0 < j < 7$.

Print one integer, the minimal number of movements that leaves the desired sequence of cars, and no other cars, on Track II.