34694번 - 슈퍼 학생

문제

대전과학고등학교 학생들은 다양한 수업을 듣느라 매 수업마다 교실을 옮겨 다녀야 해서 큰 수고로움을 겪고 있다. 태완이는 대전과학고등학교의 학생으로, 오늘도 고된 학사일정을 끝내고 잠에 들었다.

태완이는 오늘 밤 특별한 꿈을 꾸었다. 꿈속에서 태완이는 슈퍼 학생이 되어 시간표를 자유롭게 짤 수 있는 능력을 얻었다.

대전과학고등학교의 수업 주기는 일주일 단위로 운영되며, 이 문제 상황에서 일주일은 $w$일로 구성되어 있다. 태완이가 일주일 동안 들어야 하는 수업은 두 종류로 나뉜다.

1. 유연한 수업: 일주일($w$일) 중 어느 요일이든 배정 가능한 수업 (총 $a$개)
2. 고정된 수업: 매주 특정 요일에만 배정 가능한 수업 (각 요일마다 $b$개씩)

각 수업은 정해진 층에서만 진행되며, 이 층은 변경할 수 없다. 태완이는 매일 1ドル$층에서 출발하여 그날의 모든 수업을 듣고 다시 1ドル$층으로 돌아와야 한다.

태완이는 수업 사이를 이동할 때 계단을 이용한다. 현재 층에서 다음 수업이 있는 층까지의 이동 거리는 두 층 번호의 차이의 절댓값이다. 예를 들어, 3ドル$층에서 7ドル$층으로 이동하는 거리는 $|7-3|=4$이다.

수업 배정 시 지켜야 할 점은 다음과 같다.

• 각 유연한 수업은 정확히 한 번만, 일주일($w$일) 중 한 요일에 배정되어야 한다.
• 모든 고정된 수업은 반드시 매주 지정된 요일에 들어야 한다. 마찬가지로 그 요일에 정확히 한 번 배정되어야 한다.
• 각 요일 내에서 수업의 순서는 자유롭게 정할 수 있다.
• 수업 사이에 빈 시간이 있다면, 다음 수업이 시작되기 전까지 또는 그날 일과가 끝나기 전까지 현재 층에서 대기한다.
• 각 요일에 배정할 수 있는 수업 개수는 그날에 배정된 유연한 수업과 고정된 수업을 모두 포함하여 $M$개 이하다.

태완이는 일주일 동안 총 층간 이동 거리가 최소가 되도록 최적의 주간 시간표를 짜려고 한다. 이때 최소 총 층간 이동 거리를 구해 보자.

입력

첫째 줄에 네 개의 정수 $a,b,w,M$이 공백으로 구분되어 주어진다. 조건에 맞게 시간표를 짤 수 있는 경우만 입력으로 주어진다. 구체적으로, 각 수의 제한조건은 다음과 같다.

• 1ドル\le a\le 200,円 000$
• 1ドル\le b<M$
• 1ドル\le w\le 200,円 000$
• 2ドル\le M\le 200,円 000$
• $a+b\times w\le M\times w\le 200,円 000$

다음 $a$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 유연한 수업이 진행되는 층 번호 $F_i$가 주어진다. $(1\le F_i\le 10^9)$

다음 $w$개의 줄에 걸쳐 $i$번째 줄에는 반드시 $i$번째 요일에 배정되어야 하는 $b$개의 고정된 수업이 진행되는 층 번호 $S_{i,1},...,S_{i,b}$가 공백으로 구분되어 주어진다. $(1\le S_{i,j}\le 10^9)$

출력

최적의 주간 시간표를 짰을 때, 태완이가 일주일 동안 이동해야 하는 최소 총 층간 이동 거리를 출력한다.

제한

노트