Text Editor

When using a simple text editor, the user often needs to reorder lines in a specific way. When the lines are long and errors must be kept to a minimum, the easiest method is to move chunks of text from one place to another (the "cut/paste" method). You are an efficient programmer. Determine the minimum time needed to shuffle the lines into the desired order.

The file contains $N$ lines of text. The editor has a single cursor with $N+1$ possible positions: before the first line, after the last line, and between any two adjacent lines. Pressing "up" or "down" moves the cursor one line up or down. The cursor cannot move outside the text.

The Shift key selects lines. When Shift is pressed, the editor remembers the current cursor position. When Shift is released, the editor selects all lines between the current cursor position and the remembered one. After releasing Shift, press Ctrl+X to cut the selected lines. They are copied to the clipboard and removed from the text. To paste the cut fragment back, move the cursor to the desired position with "up" and "down", then press Ctrl+V. After pasting, the fragment is removed from the clipboard.

When a fragment is cut, all following lines move up. When it is pasted, they move down. The text never contains empty lines. After a cut, the cursor moves up to the line where the cut fragment began, unless it is already there. After a paste, the cursor moves down and ends up right after the inserted text.

Every action takes a predefined time that depends on user skill. Initially, the cursor is before the first line of the text.

The first line contains one integer $N$, the number of lines in the text editor ($2 \le N \le 8$). The second line contains six integers $t_1, t_2, \ldots, t_6$, the time in milliseconds of each action ($1 \le t_i \le 100$). The third line contains $N$ distinct integers from 1 to $N$, the initial order of the lines. The fourth line contains $N$ distinct integers from 1 to $N$, the order in which the lines must be placed at the end.

Print two integers on the first line: $T$, the total time of the plan in milliseconds, and $K$, the number of actions in the plan. Then print the $K$ actions in execution order, one per line:

• Up: press "up" (takes $t_1$ milliseconds).
• Down: press "down" (takes $t_2$ milliseconds).
• Shift-Press: press and hold Shift (takes $t_3$ milliseconds).
• Shift-Release: release Shift (takes $t_4$ milliseconds).
• Ctrl+X: press the combination Ctrl+X (takes $t_5$ milliseconds).
• Ctrl+V: press the combination Ctrl+V (takes $t_6$ milliseconds).

The example is a reversal of six lines. Every action takes 100 milliseconds or a bit less. The optimal plan is shown in an animated gif image, which can be downloaded near these problem statements.