Super Ball

먼 미래에 공을 만드는 회사가 있다. 공은 양파처럼 안쪽부터 바깥쪽까지 $N$개 층이 겹겹이 쌓인 구조이다. 각 층에는 $1$부터 $L$까지 종류 번호가 붙는다.

공장은 $F$개 있고 각 공장은 만들 수 있는 층 종류가 따로 정해져 있다. 한 공장이 여러 종류를 만들 수 있고, 한 종류를 여러 공장이 만들 수 있다. 공장에서 층을 하나 만들 때마다 생산 비용을 내고, 공장에서 층을 하나 해체할 때마다 재활용 비용을 낸다. 만들 수 없는 종류는 비용이 $-1$로 표시된다.

생산은 가장 안쪽 층 $G_1$부터 바깥쪽 층 $G_N$까지 순서대로 진행된다. 연속된 두 층을 서로 다른 공장에서 만들면 두 공장 사이의 이동 비용 $C$를 낸다. 같은 공장에서 연속해서 만들면 이동 비용은 $0$이다. 재활용은 바깥쪽 층 $G_N$부터 안쪽 층 $G_1$까지 역순으로 진행되며 이동 비용도 같은 방식으로 낸다. 완성된 공을 고객에게 보내거나 고객에게서 회수할 때는 어느 공장에서 시작하고 어느 공장에서 끝나도 비용이 들지 않는다. 생산과 재활용 비용의 합이 가장 작아지도록 공장을 선택했을 때 총비용을 구한다.

첫째 줄에 공장의 수 $F$와 층 종류의 수 $L$이 주어진다 ($1 \le F \le 500$, $1 \le L \le 500$). 공장은 $1$부터 $F$까지, 층 종류는 $1$부터 $L$까지 번호가 붙는다.

다음 $3F$줄에 공장 정보가 한 공장씩 세 줄로 주어진다. 공장 $f$의 첫째 줄에는 $F$개 정수 $C_{f,1}, C_{f,2}, \dots, C_{f,F}$가 주어진다 ($0 \le C_{f,i} \le 10^3$). $C_{f,i}$는 공장 $f$에서 공장 $i$로 공을 옮기는 비용이다. 둘째 줄에는 $L$개 정수 $D_1, D_2, \dots, D_L$이 주어진다 ($-1 \le D_i \le 10^3$). $D_i$는 이 공장에서 종류 $i$인 층을 하나 생산하는 비용이고 $-1$이면 생산할 수 없다. 셋째 줄에는 $L$개 정수 $R_1, R_2, \dots, R_L$이 주어진다 ($-1 \le R_i \le 10^3$). $R_i$는 이 공장에서 종류 $i$인 층을 하나 재활용하는 비용이고 $-1$이면 재활용할 수 없다.

마지막 줄에는 공의 구성 정보가 주어진다. 첫 정수 $N$은 층의 개수이고 ($1 \le N \le 500$) 뒤따르는 $N$개 정수 $G_1, G_2, \dots, G_N$은 안쪽부터 바깥쪽까지 각 층의 종류이다 ($1 \le G_i \le L$).

생산 비용과 재활용 비용을 합한 총비용의 최솟값을 한 줄에 출력한다.

처음과 끝의 이동은 무료이므로 생산과 재활용은 서로 영향을 주지 않는다. 전체 최솟값은 생산 과정의 최솟값과 재활용 과정의 최솟값의 합과 같다. 각 과정은 층 순서대로 공장을 선택하는 동적 계획법으로 구할 수 있다. 생산은 $G_1$부터 $G_N$까지, 재활용은 $G_N$부터 $G_1$까지 진행한다.