Minimizing Rotations to Open the 12-Knob Door

A mysterious door has a mechanism consisting of 12 knobs. Each knob has 4 states, represented by the numbers \(1\) to \(4\). The only allowed operation is to rotate a chosen knob forward (in one direction only): from state \(1\) to \(2\), \(2\) to \(3\), \(3\) to \(4\), and \(4\) turns back to \(1\). However, when you rotate a knob, it triggers exactly one other knob to rotate by one step in the same direction. Which knob gets rotated depends on the knob you rotated and its state before the rotation. Note that this triggered rotation does not cause any further rotations (i.e. no chain reaction).

The trigger relationships for each knob are provided in the input. In particular, for knob \(i\) (\(1 \le i \le 12\)), when it is rotated while in state \(s\) (where \(s \in \{1,2,3,4\}\)), it will automatically rotate knob \(p\) (given in the input for that knob and that state); note that \(p\) is in \(\{1,\dots,12\}\). The door will open when all knobs are in state \(1\).

Because the knobs are old and rotating them is very tiring, Steve wants to open the door using the least number of rotations possible. Your task is to compute the minimum number of rotations required so that all knobs become state \(1\). It is guaranteed that the mechanism is in a configuration that can be unlocked.

inputFormat

The input consists of 13 lines:

1. The first line contains 12 integers \(a_1, a_2, \dots, a_{12}\), where \(a_i\) (\(1 \le a_i \le 4\)) is the current state of the \(i\)-th knob.</p>
2. Then follow 12 lines. The \(i\)-th of these lines contains 4 integers. The \(j\)-th integer on the \(i\)-th line (\(1 \le j \le 4\)) indicates the knob number (in \(1 \le p \le 12\)) that is automatically rotated when knob \(i\) is rotated while in state \(j\).</p> </ol>

   Note: When a knob is rotated, it always increments from \(s\) to \((s \bmod 4) + 1\) and then triggers the corresponding knob rotation (which also rotates it by one step forward).

   outputFormat

   Output a single integer indicating the minimum number of rotations required to set all knobs to state \(1\>.

   sample

   1 1 1 1 1 1 1 1 1 1 1 1
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4
   1 2 3 4

   0