요리 강좌 |
---|
여러분은 요리에 관심이 많아 요리 자격증을 취득하려고 한다. 요리 자격증을 취득하기 위해서는 총 M개의 강좌를 순서대로 한 번씩만 수강해야 한다. 이 요리 강좌는 N개의 학원에서 수강할 수 있는데, 학원마다 강좌별 수강비용은 다를 수 있다. 아래 표는 M = 5, N = 4인 경우, 학원별, 강좌별 수강비용의 예를 보여준다. 여러분은 비용을 줄이기 위해 중간에 학원을 변경할 수 있는데, 학원을 변경할 때마다 T의 추가 비용이 든다. 단, 학원 변경은 다음 규칙을 지켜야 한다.
예를 들어, S = 2, E = 3, T = 2이고, 위 수강비용 표와 불허용 학원 표가 주어졌을 때, 강좌 순서대로 수강하는 학원의 번호가
강좌 비용, 강좌 선택에 필요한 규칙 정보가 주어졌을 때, 모든 강좌를 순서대로 수강하기 위해 필요한 최소 비용을 구하시오. |
입력 | |
---|---|
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 학원의 개수 N과 강좌 개수 M(3 ≤ N ≤ 3,000, 1 ≤ M ≤ 3,000, N × M ≤ 3,000,000), 학원 한 곳에서 연속 수강 가능한 최소 강좌 개수 S와 최대 강좌 개수 E(1 ≤ S ≤ E ≤ M), 그리고 학원 변경 비용 T(0 ≤ T ≤ 35,000)가 주어진다. 다음 N개의 줄에는 각 학원의 강좌별 수강비용이 주어진다. (수강비용은 1 이상 35,000 이하이다.) 처음 줄에는 학원1의 M개의 수강비용이 강좌 순서대로 공백을 사이에 두고 주어지고, 그 다음 줄부터 학원2, 학원3, ... , 학원N의 정보가 한 줄에 하나씩 순서대로 주어진다. 그 다음 N개의 줄에는 학원마다 불허용 학원 번호가 순서대로 주어진다. |
출력 | |
---|---|
표준 출력으로 최소 비용을 출력한다. |
예시 | |||
---|---|---|---|
1 | 입력 | 4 5 2 3 2 1 2 1 3 8 1 2 3 7 2 1 8 8 1 2 10 1 1 8 8 2 3 4 3 | |
출력 | 9 | ||
2 | 입력 | 4 5 1 1 0 1 2 1 3 8 1 2 3 7 2 1 8 8 1 2 10 1 1 8 8 2 3 4 3 | |
출력 | 9 |