Super Ball

A company in the distant future builds balls. Each ball has $N$ layers wrapped around each other like an onion, numbered from the innermost layer $G_1$ to the outermost layer $G_N$. Each layer has a type between $1$ and $L$.

There are $F$ factories. Each factory can build only certain layer types. One factory can handle several types, and one type can be handled by several factories. Building a layer at a factory costs the production price of that factory, and taking a layer apart at a factory costs its recycling price. A price of $-1$ means the factory cannot do that job.

Production runs from the innermost layer $G_1$ to the outermost layer $G_N$. When two consecutive layers are built at different factories, the ball is moved between them and the transfer cost $C$ applies. Two consecutive layers built at the same factory need no transfer. Recycling runs in reverse, from the outermost layer $G_N$ down to the innermost layer $G_1$, with the same transfer rule. Pickup of the finished ball and return of the used ball are free from any factory. Choose factories for every layer in both directions so the sum of production and recycling costs is as small as possible.

The first line holds the number of factories $F$ and the number of layer types $L$ ($1 \le F \le 500$, $1 \le L \le 500$). Factories are numbered $1$ to $F$ and layer types $1$ to $L$.

The next $3F$ lines describe the factories, three lines per factory. The first line for factory $f$ holds $F$ integers $C_{f,1}, C_{f,2}, \dots, C_{f,F}$ ($0 \le C_{f,i} \le 10^3$). $C_{f,i}$ is the cost of moving the ball from factory $f$ to factory $i$. The second line holds $L$ integers $D_1, D_2, \dots, D_L$ ($-1 \le D_i \le 10^3$). $D_i$ is the cost of producing one layer of type $i$ at this factory, and $-1$ means production is impossible. The third line holds $L$ integers $R_1, R_2, \dots, R_L$ ($-1 \le R_i \le 10^3$). $R_i$ is the cost of recycling one layer of type $i$ at this factory, and $-1$ means recycling is impossible.

The last line describes the ball. It starts with the layer count $N$ ($1 \le N \le 500$), followed by $N$ integers $G_1, G_2, \dots, G_N$ listing the type of each layer from the inside out ($1 \le G_i \le L$).

Print one integer: the smallest possible sum of production and recycling costs.

Pickup and return are free, so production and recycling do not affect each other. The answer is the smallest production cost plus the smallest recycling cost. Each part is a dynamic program over the layer order: production follows $G_1$ to $G_N$, and recycling follows $G_N$ down to $G_1$.