요리 강좌

요리 자격증을 따려면 강좌1부터 강좌M까지 $M$개의 강좌를 순서대로 한 번씩 수강해야 한다. 강좌는 $N$개의 학원에서 들을 수 있고, 같은 강좌라도 학원마다 수강비용이 다르다.

아래 표는 $M = 5$, $N = 4$인 경우의 수강비용 예시다.

비용을 줄이려고 중간에 학원을 바꿀 수 있다. 학원을 한 번 바꿀 때마다 추가 비용 $T$가 든다. 학원을 바꿀 때는 다음 두 규칙을 지켜야 한다.

규칙 (a). 한 학원에서 연속으로 수강하는 강좌 수는 최소 $S$개, 최대 $E$개다. 다만 강좌M을 수강하는 학원에서는 $S$개를 연속으로 채우지 않아도 된다. 이 학원에서도 최대 $E$개 제한은 그대로 적용된다.

$S = 2$, $E = 3$이라고 하자. 강좌1을 학원1에서 들었다면 강좌2도 학원1에서 들어야 하고, 강좌3은 학원1에서 들어도 되고 다른 학원에서 들어도 된다. 강좌1부터 강좌3까지를 학원1에서 들었다면 강좌4는 반드시 다른 학원에서 들어야 한다. $S = 1$, $E = 2$라면 강좌1과 강좌2를 학원3에서, 강좌3과 강좌4를 학원1에서, 강좌5를 다시 학원3에서 듣는 것도 가능하다.

규칙 (b). 학원마다 불허용 학원이 하나씩 정해져 있다. 학원 $q$의 불허용 학원이 학원 $p$이면, 학원 $p$에서 학원 $q$로 바꿀 수 없다.

아래 표에서 학원1의 불허용 학원은 학원2이므로 학원2에서 학원1로 바로 바꾸는 것은 불가능하다. 학원2 → 학원4 → 학원1처럼 다른 학원을 거쳐 옮기는 것은 가능하다.

$S = 2$, $E = 3$, $T = 2$이고 위 두 표가 주어졌다고 하자. 강좌 순서대로 수강한 학원 번호가

• 1 → 1 → 1 → 1 → 3이면 한 학원에서 강좌 4개를 연속으로 듣게 되어 규칙 (a)에 어긋난다.
• 2 → 2 → 1 → 1 → 1이면 학원2에서 학원1로 바꾸므로 규칙 (b)에 어긋난다.
• 3 → 3 → 1 → 1 → 3이면 가능하고, 전체 비용은 $1 + 8 + T + 1 + 3 + T + 2 = 19$다.
• 1 → 1 → 1 → 3 → 3이면 가능하고, 전체 비용은 $1 + 2 + 1 + T + 1 + 2 = 9$다.

수강비용과 불허용 학원 정보가 주어질 때, 강좌M까지 모두 순서대로 수강하는 데 드는 최소 비용을 구하시오.

첫째 줄에 학원 수 $N$, 강좌 수 $M$, 한 학원에서 연속으로 수강할 수 있는 최소 강좌 수 $S$, 최대 강좌 수 $E$, 학원 변경 비용 $T$가 공백을 사이에 두고 주어진다. ($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$)

다음 $N$개 줄에는 학원별 수강비용이 주어진다. $i$번째 줄에는 학원 $i$의 강좌1부터 강좌M까지의 수강비용 $M$개가 공백을 사이에 두고 주어진다. 각 수강비용은 $1$ 이상 $35000$ 이하의 정수다.

그다음 $N$개 줄에는 학원1부터 학원N까지의 불허용 학원 번호가 한 줄에 하나씩 주어진다. 각 번호는 $1$ 이상 $N$ 이하이고, 자기 자신의 번호와는 다르다.

첫째 줄에 최소 비용을 출력한다.