Задача №114351. Под дождём
Сегодня Полина со своими сокомандниками написала 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
Сдать: для сдачи задач необходимо войти в систему