텍스트 편집기

간단한 텍스트 편집기를 쓸 때 사용자는 줄을 특정한 순서로 재배열해야 하는 경우가 많다. 줄이 길고 실수를 최소화해야 한다면, 가장 쉬운 방법은 텍스트 덩어리를 한 곳에서 다른 곳으로 옮기는 것이다("잘라내기/붙여넣기" 방식). 당신은 효율적인 프로그래머이다. 줄들을 원하는 순서로 섞는 데 필요한 최소 시간을 구하라.

파일에는 $N$개의 줄이 있다. 편집기에는 커서가 하나 있으며, 커서가 놓일 수 있는 위치는 $N+1$개이다. 첫 번째 줄 앞, 마지막 줄 뒤, 그리고 인접한 두 줄 사이이다. "위" 또는 "아래"를 누르면 커서가 한 줄 위 또는 아래로 움직인다. 커서는 텍스트 밖으로 움직일 수 없다.

Shift 키로 줄을 선택한다. Shift를 누르면 편집기는 현재 커서 위치를 기억한다. Shift를 떼면 현재 커서 위치와 기억해 둔 위치 사이의 모든 줄이 선택된다. Shift를 뗀 뒤에는 Ctrl+X를 눌러 선택한 줄을 잘라낸다. 잘라낸 줄은 클립보드에 복사되고 텍스트에서는 제거된다. 잘라낸 부분을 다시 붙여넣으려면 "위"와 "아래"로 커서를 원하는 위치에 옮긴 뒤 Ctrl+V를 누른다. 붙여넣은 후에는 그 부분이 클립보드에서 사라진다.

줄을 잘라내면 그 뒤의 줄들이 모두 위로 올라온다. 붙여넣으면 뒤의 줄들이 아래로 밀려난다. 텍스트에 빈 줄은 생기지 않는다. 잘라낸 뒤 커서는 잘라낸 부분이 시작된 줄로 올라간다. 이미 그 줄에 있다면 움직이지 않는다. 붙여넣은 뒤 커서는 아래로 움직여 삽입된 텍스트 바로 뒤에 놓인다.

모든 동작에는 사용자의 숙련도에 따라 정해진 시간이 걸린다. 처음에 커서는 텍스트의 첫 번째 줄 앞에 있다.

첫 줄에는 정수 $N$이 주어진다. 이는 텍스트 편집기의 줄 수이다($2 \le N \le 8$). 둘째 줄에는 여섯 개의 정수 $t_1, t_2, \ldots, t_6$이 주어지며, 각 동작이 걸리는 밀리초이다($1 \le t_i \le 100$). 셋째 줄에는 1부터 $N$까지의 서로 다른 정수 $N$개가 주어지며, 이는 줄의 초기 순서이다. 넷째 줄에는 1부터 $N$까지의 서로 다른 정수 $N$개가 주어지며, 이는 마지막에 줄들이 놓여야 할 순서이다.

첫 줄에 두 정수를 출력한다. $T$는 계획 전체에 걸리는 시간(밀리초)이고, $K$는 계획에 포함된 동작의 개수이다. 이어서 실행 순서대로 $K$개의 동작을 한 줄에 하나씩 출력한다.

• Up: "위"를 누른다($t_1$ 밀리초가 걸린다).
• Down: "아래"를 누른다($t_2$ 밀리초가 걸린다).
• Shift-Press: Shift를 누른 채 유지한다($t_3$ 밀리초가 걸린다).
• Shift-Release: Shift를 뗀다($t_4$ 밀리초가 걸린다).
• Ctrl+X: Ctrl+X를 누른다($t_5$ 밀리초가 걸린다).
• Ctrl+V: Ctrl+V를 누른다($t_6$ 밀리초가 걸린다).

예시는 여섯 줄을 뒤집는 문제이다. 모든 동작은 100밀리초이거나 그보다 조금 적게 걸린다. 최적의 계획은 애니메이션 GIF로 기록되어 있으며, 이 문제 설명 근처에서 내려받을 수 있다.