시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 663 | 190 | 134 | 34.271% |
여러분은 요리에 관심이 많아 요리 자격증을 취득하려고 한다. 요리 자격증을 취득하기 위해서는 총 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개의 줄에는 학원마다 불허용 학원 번호가 순서대로 주어진다.
표준 출력으로 최소 비용을 출력한다.
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
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