29695번 - 기지방호 서브태스크

문제

오늘부터 $L$일 동안 훈련 기간이다. 훈련 기간에 매일 부대원들은 기지방호 전술집에서 선별한 진법들을 시연해야 한다.

훈련을 위해 기지방호 전술집에서 $F$개의 진법을 선별하여 각각 1ドル$번부터 $F$번까지 번호를 붙였고, $x$번에 대한 진법을 $C[x]$$(1 \le x \le F)$로 나타내기로 했다. 각 진법은 훈련하는 장소에 맞추어 $N \times M$ 칸으로 주어진다. $C[x]_{ij}$는 진법 $C[x]$의 $i$번째 행, $j$번째 열을 의미하며, 해당 칸에 사람이 서 있어야 하면 1ドル,ドル 아니면 0ドル$으로 주어진다. 다만 항상 $C[1]$은 모든 $i,ドル $j$ $(1 \le i \le N; 1 \le j \le M)$에 대해 $C[1]_{ij} = 0$ 을 만족한다.

훈련의 첫째 날은 $C[1]$ 진법부터 시작하며, 둘째 날부터는 전날의 마지막 진법에서 시작한다. 이후 하루가 끝날 때까지 $T$회에 걸쳐 추가로 진법을 시연한다.

진법이 바뀜에 따라 병사들의 피로도는 다음과 같이 누적된다. 현재 시연 중인 진법이 $C[A],ドル 다음에 시연할 진법이 $C[B]$ 라면 피로도는 $C[A]_{ij}$와 $C[B]_{ij}$가 다른 모든 $(i, j)$ 쌍의 개수를 제곱한 값만큼 더해진다. $(1 \le i \le N; 1 \le j \le M)$

현재 날마다 마지막으로 시연할 진법들만 정해져 있으므로, 주임원사님은 으뜸병사를 불러 선별된 진법들로 나머지 시연할 진법들을 잘 채워서 병사들의 피로도를 최소화하는 루틴으로 만들라고 명령했다. 으뜸병사를 도와서 피로도를 최소화하는 루틴을 짰을 때, 총피로도는 어느 정도인지 한번 알아보자.

입력

첫 번째 줄에 기지방호 전술집에서 선별한 진법의 개수 $F,ドル 훈련 기간 $L,ドル 하루에 시연할 진법의 개수 $T,ドル 그리고 훈련 장소의 크기 $N,ドル $M$이 공백으로 구분되어 정수로 주어진다.

이후 두 번째 줄부터 각 진법마다 $N$줄씩 $F \times N$줄에 걸쳐 $C[1], C[2], \cdots, C[F]$ 진법의 정보가 순서대로 주어진다.

각 진법의 정보는 $N$줄에 걸쳐 $M$개의 값이 공백으로 구분되어 정수로 주어진다. $i$번째 줄의 $j$번째 값이 $C[x]_{ij}$이며, 각 값은 0ドル$ 또는 1ドル$로 주어진다.

이후 첫 번째 날부터 $L$번째 날까지 마지막으로 시연할 진법의 번호 $l_1, l_2, \cdots, l_L$이 공백으로 구분되어 정수로 주어진다.

출력

첫 번째 줄에 피로도를 최소화하는 루틴의 총피로도를 출력한다.

제한

• 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$
• 모든 $i,ドル $j$ $(1 \le i \le N; 1 \le j \le M)$에 대해 $C[1]_{ij} = 0$

서브태스크

힌트