상영실의 공통 연장 시간

문제

한 영화관에서 특별 상영회를 준비한다. 상영할 영화 N편에는 반드시 지켜야 하는 순서가 있으며, 이 순서대로 1번부터 N번까지 번호가 붙어 있다. 영화관은 상영실 M개를 정해진 순서로 사용한다. 각 상영실에는 원래 사용할 수 있는 시간이 정해져 있고, 상영실마다 이 시간은 다를 수 있다. 운영자는 모든 영화를 상영실에 나누어 배정하려고 한다. 각 영화는 정확히 하나의 상영실에서 처음부터 끝까지 상영해야 하며, 영화를 나누어 상영할 수 없다. 같은 상영실에 배정된 영화들은 영화 번호순으로 상영한다. 또한 앞선 상영실에 배정된 모든 영화의 번호는 뒤의 상영실에 배정된 모든 영화의 번호보다 작아야 한다. 따라서 영화를 배정받은 상영실은 전체 영화 순서에서 연속한 구간을 담당하게 된다. 어떤 상영실에는 영화를 한 편도 배정하지 않아도 된다. 같은 상영실에서 연이어 두 영화를 상영할 때는 정확히 B분의 정리 시간이 필요하다. 첫 영화 전과 마지막 영화 후에는 정리 시간이 필요하지 않다. 영화가 k편 배정된 상영실의 사용 시간은 k가 양수이면 그 영화들의 상영 시간 합에 B×(k-1)을 더한 값이며, k가 0이면 0분이다. 서로 다른 상영실 사이에는 별도의 정리 시간을 더하지 않는다. 필요하다면 영화관은 모든 상영실의 사용 가능 시간을 같은 정수 X분만큼 연장할 수 있다. j번 상영실의 원래 사용 가능 시간이 C_j분이면 연장 후에는 C_j+X분까지 사용할 수 있다. 사용 시간이 이 값과 정확히 같아도 배정할 수 있다. 연장 시간 X는 0 이상의 정수이며, 영화를 배정하지 않은 상영실에도 같은 연장 규칙이 적용된다. 영화 순서와 상영실 순서를 유지하면서 모든 영화를 상영할 수 있도록 하는 가장 작은 X를 구한다. 상영실에 배정할 영화 수가 같을 필요는 없다. 연장 시간에는 별도의 상한이 없고 상영실이 적어도 하나 있으므로 가능한 배정은 항상 존재한다. 실제 배정 방법은 출력하지 않는다.

입력

첫째 줄에 정수 N, M, B가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 16,000, 1 ≤ M ≤ 16,000, 0 ≤ B ≤ 1,000,000이다.
둘째 줄에 영화 순서대로 상영 시간 A_1, A_2, ..., A_N이 주어진다. 각 A_i는 1 이상 1,000,000 이하의 정수다.
셋째 줄에 상영실 순서대로 원래 사용 가능 시간 C_1, C_2, ..., C_M이 주어진다. 각 C_j는 0 이상 1,000,000 이하의 정수다.
시간의 단위는 모두 분이다.

출력

모든 영화를 규칙에 맞게 배정할 수 있는 가장 작은 공통 연장 시간 X를 정수 하나로 출력한다.

4 2 2
4 3 5 2
6 7

3

3 3 4
8 2 3
1 8 9

0

3 1 5
2 2 2
0

16

출처: Devin.KR 자체 제작