407261: GYM102739 C Под дождём

C. Под дождёмограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Сегодня Полина со своими сокомандниками написала 5-часовую тренировку в школе и теперь собирается возвращаться домой. К сожалению, на улице пошёл дождь, а зонт девочка, как обычно, не взяла. К счастью, у неё есть приложение, показывающее не только погоду, но и интенсивность осадков, которым она сейчас и собирается воспользоваться, чтобы промокнуть как можно меньше (хотя могла бы воспользоваться им утром и просто взять зонт, но это слишком просто).

Обычно, возвращаясь из школы, Полина сначала идёт по «обычной» улице, а затем по аллее сквера, которую укрывают деревья с раскидистой кроной. Крона деревьев сможет задержать часть капель, что позволит Полине меньше намокнуть.

Время, в течение которого Полина будет идти по «обычной» улице, составляет $$$t_1$$$ минут, затем в течение времени $$$t_2$$$ минут она будет идти под деревьями (пока не дойдёт до дома).

Полине нужно оказаться дома не позднее, чем через $$$d$$$ $$$(t_1 + t_2 \le d)$$$ единиц времени от текущего момента (иначе она опоздает на ужин).

Полинино приложение говорит, что в $$$j$$$-ю минуту интенсивность дождя составляет $$$r_j$$$. Крона деревьев снижает интенсивность дождя на величину $$$s$$$ (но не может сделать её отрицательной).

Полина хочет минимизировать суммарную интенсивность дождя, прольющегося на неё.

Ваша задача — определить, в какой момент Полине следует выйти из школы, а также суммарную интенсивность дождя, которая ей достанется в этом случае.

Входные данные

В первой строке содержатся целые числа $$$t_1$$$, $$$t_2$$$, $$$d$$$, $$$s$$$ $$$(1 \le t_1, \, t_2, \, d \le 10^6, \, t_1 + t_2 \le d, \, 1 \le s \le 10^5)$$$, $$$t_1$$$ — время пути по «обычной» улице; $$$t_2$$$ — время пути по аллее, $$$d$$$ — момент времени, не позже которого Полина должна оказаться дома, $$$s$$$ — величина уменьшения интенсивности дождя под кронами.

Во второй строке содержится $$$d$$$ целых чисел $$$r_1, r_2, \ldots, r_d$$$ $$$(1 \le r_j \le 10^5, \, j = 1, 2, \ldots, d)$$$ — интенсивность дождя.

Выходные данные

Выведите два целых числа: момент времени, в который Полине следует выйти из школы, и суммарную интенсивность дождя, под которым она пройдёт.

Если существует несколько вариантов ответа, выведите наиболее ранний момент времени.

Система оценки

$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } \\ \hline 1 & 28 & \text {Входные данные не превышают 100 } & \text { подзадача } \\ \hline 2 & 45 & t_1, t_2, d \le 10^5 & \text { подзадача } & 1 \\ \hline 3 & 27 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$

ПримерыВходные данные

2 3 10 5
1 1 1 8 7 1 1 2 10 1

Выходные данные

0
7

Входные данные

5 7 17 6
5 7 8 4 2 2 7 6 5 7 4 8 8 7 3 6 1

Выходные данные

3
27