Base Defense

Starting today, the training period lasts $L$ days. Every day, the unit members must demonstrate formations selected from the base defense formation catalog.

For the training, $F$ formations are selected from the catalog and numbered 1 to $F$. Formation $x$ is written $C[x]$ ($1 \le x \le F$). Each formation is an $N \times M$ grid matching the training site. $C[x]_{ij}$ is the cell in row $i$ and column $j$ of $C[x]$, equal to 1 if a soldier must stand in that cell and 0 otherwise. $C[1]$ satisfies $C[1]_{ij} = 0$ for all $i$, $j$ ($1 \le i \le N$, $1 \le j \le M$).

On the first day, the routine starts from $C[1]$. From the second day on, each day starts from the last formation of the previous day. Until the day ends, $T$ more formations are demonstrated.

Each change of formation adds fatigue. If the formation being demonstrated is $C[A]$ and the next one is $C[B]$, the fatigue added is the square of the number of pairs $(i, j)$ where $C[A]_{ij}$ and $C[B]_{ij}$ differ ($1 \le i \le N$, $1 \le j \le M$).

The last formation of each day is already fixed. The chief sergeant ordered the lead soldier to fill the remaining demonstrations with the selected formations so that the total fatigue is minimized. Find the total fatigue of that routine.

The first line contains $F$, $L$, $T$, $N$, and $M$, separated by spaces.

From the second line on, the information for $C[1], C[2], \cdots, C[F]$ is given in order, using $F \times N$ lines in total. Each formation takes $N$ lines with $M$ values separated by spaces. The $j$-th value on the $i$-th line is $C[x]_{ij}$, and each value is 0 or 1.

Finally, the numbers $l_1, l_2, \cdots, l_L$ of the formation to be demonstrated last on day 1 through day $L$ are given, separated by spaces.

Print the total fatigue of the routine that minimizes fatigue on the first line.

• $2 \le F \le 50$
• $1 \le L \le 1\,000\,000$
• $1 \le T \le 1\,000\,000$
• $1 \le N, M \le 50$
• $1 \le l_k \le F$ ($1 \le k \le L$)
• For all $i$, $j$ ($1 \le i \le N$, $1 \le j \le M$), $C[1]_{ij} = 0$