공연 회차 나누기

문제

작은 공연장에서 하루 동안 N개의 팀이 정해진 순서대로 무대에 올라야 한다. i번째 팀의 공연 시간은 t_i분이며, 팀의 순서는 바꿀 수 없다. 공연장은 팀들을 순서대로 연속한 묶음으로 나누어 여러 회차로 운영한다. 회차는 최대 K개까지 열 수 있고, 모든 팀은 정확히 하나의 회차에 속해야 하며, 비어 있는 회차는 만들지 않는다. 회차에는 다음 규칙이 있다. - 한 회차에 들어가는 팀은 최대 W팀이다. - 한 회차 안에서 이웃한 두 팀 사이에는 무대를 정리하는 시간 g분이 반드시 들어간다. 따라서 팀이 c개인 회차의 길이는 그 팀들의 공연 시간의 합에 g × (c − 1)분을 더한 값이다. 회차의 처음과 끝에는 정리 시간이 붙지 않는다. 모든 팀을 위 규칙대로 배정할 때, 가장 긴 회차의 길이를 최소로 만들고 싶다. 그 최솟값을 구하시오. 규칙을 지키는 배정이 하나도 없다면 -1을 출력한다.

입력

첫째 줄에 N, K, W, g가 공백으로 구분되어 주어진다(1 ≤ N ≤ 200,000, 1 ≤ K ≤ N, 1 ≤ W ≤ N, 0 ≤ g ≤ 1,000). 둘째 줄에 t_1, ..., t_N(1 ≤ t_i ≤ 1,000, 정수)이 주어진다.

출력

가장 긴 회차 길이의 최솟값을 한 줄에 출력한다. 배정이 불가능하면 -1을 출력한다.

5 2 3 1
4 2 3 5 1

11

5 1 3 1
4 2 3 5 1

-1

3 3 1 5
7 7 7

7

출처: Devin.KR 자체 제작