Cooking Courses

To earn a cooking certificate you must take $M$ courses, course 1 through course $M$, in that order and exactly once each. The courses are offered by $N$ academies, and the fee for the same course can differ from academy to academy.

The table below shows example fees for $M = 5$ and $N = 4$.

You may switch academies partway to cut the cost. Each switch adds a fee of $T$. A switch must obey the two rules below.

Rule (a). The number of courses taken consecutively at one academy is at least $S$ and at most $E$. The academy where you take course $M$ is exempt from the lower bound $S$. The upper bound $E$ still applies there.

Suppose $S = 2$ and $E = 3$. If you take course 1 at academy 1, course 2 must also be taken at academy 1, while course 3 may be taken at academy 1 or at another academy. If you take courses 1 through 3 at academy 1, course 4 must be taken at another academy. With $S = 1$ and $E = 2$ it is possible to take courses 1 and 2 at academy 3, courses 3 and 4 at academy 1, and course 5 at academy 3 again.

Rule (b). Every academy has exactly one disallowed academy. If the disallowed academy of academy $q$ is academy $p$, you cannot switch from academy $p$ to academy $q$.

In the table below the disallowed academy of academy 1 is academy 2, so switching straight from academy 2 to academy 1 is impossible. Moving through another academy, as in academy 2 → academy 4 → academy 1, is possible.

Suppose $S = 2$, $E = 3$, $T = 2$, and the two tables above. Reading the academy numbers in course order:

• 1 → 1 → 1 → 1 → 3 takes four courses in a row at one academy, which breaks rule (a).
• 2 → 2 → 1 → 1 → 1 switches from academy 2 to academy 1, which breaks rule (b).
• 3 → 3 → 1 → 1 → 3 is allowed, and the total cost is $1 + 8 + T + 1 + 3 + T + 2 = 19$.
• 1 → 1 → 1 → 3 → 3 is allowed, and the total cost is $1 + 2 + 1 + T + 1 + 2 = 9$.

Given the fees and the disallowed academies, find the minimum cost of taking all $M$ courses in order.

The first line contains the number of academies $N$, the number of courses $M$, the minimum number $S$ and the maximum number $E$ of courses that can be taken consecutively at one academy, and the switching fee $T$, separated by spaces. ($3 \le N \le 3000$, $1 \le M \le 3000$, $N \times M \le 3000000$, $1 \le S \le E \le M$, $0 \le T \le 35000$)

Each of the next $N$ lines contains the fees of one academy. The $i$-th of these lines contains $M$ integers, the fees of academy $i$ for course 1 through course $M$, separated by spaces. Each fee is an integer between $1$ and $35000$.

Each of the next $N$ lines contains the number of the disallowed academy of academy 1 through academy $N$, one per line. Each number is between $1$ and $N$ and differs from the number of the academy itself.

Print the minimum cost on the first line.