E. Фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

С точки зрения кота Бенедикта, каждое время суток интересно по-своему. Когда наступает вечер, в парке включают фонари, и Бенедикту из окна видна цепочка из $$$n$$$ светящихся шаров.

Однако лампочки в фонарях иногда перегорают, и работникам парка приходится их заменять. Работники парка полагают, что сразу же заменять перегоревшую лампочку необязательно. Они дожидаются первого момента времени, когда перегоревших лампочек станет не менее $$$m$$$, и только тогда отправляются менять их на новые.

Работники парка, отправляясь менять лампочки, действуют следующим образом.

Они берут лампочки со склада в нужном для замены всех перегоревших лампочек количестве (обратите внимание, что одновременно могут перегорать несколько лампочек, поэтому количество взятых лампочек может превосходить $$$m$$$) и двигаются в направлении от первого к последнему фонарю.

Все лампочки занумерованы номерами от $$$1$$$ до $$$s$$$ ($$$n \le s$$$). Работники устанавливают лампочки в соответствии с их номерами:

  • Лампочка с большим номером не может быть использована для замены, пока не использованы все лампочки с меньшими номерами;
  • Если две лампочки взяты в рамках одного «набора для замены», то лампочка с меньшим номером будет установлена в фонарь с меньшим номером (независимо от того, в каком порядке фонари перегорали).

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

Вам известна длительность работы в днях лампочки в каждом фонаре и каждой лампочки на складе.

Считайте, что все лампочки в фонарях установлены сегодня, и это первый день работы лампочек в фонарях. Из соображений общности установку лампочек будем считать первой состоявшейся заменой. Лампочка, находящаяся на складе, не расходует свой ресурс, пока не будет установлена в фонаре.

Работники парка интересуются номером дня $$$k$$$, в который они проинформируют начальство о необходимости закупки лампочек (и, соответственно, у них появится возможность отправиться в отпуск).

Кот Бенедикт хотел бы узнать:

  • какое максимальное количество дней пройдёт между двумя последовательными заменами лампочек в каком-либо одном фонаре;
  • какое максимальное суммарное количество дней какой-либо один фонарь будет оставаться не работающим.

Оба этих значения кот Бенедикт хочет узнать на отрезке от сегодняшнего дня до дня $$$k$$$.

Ваша задача — определить эти три числа.

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

В первой строке содержатся целые числа $$$n$$$, $$$s$$$, $$$m$$$ $$$\left(1 \le n \le s \le 2 \cdot 10^5; 1 \le m \le n \right)$$$ — количество фонарей, количество лампочек на складе, количество перегоревших лампочек, которое с точки зрения работников парка является поводом отправиться их менять.

Во второй строке содержится $$$n$$$ целых чисел $$$d_1, d_2, \ldots, d_n$$$ $$$(1 \le d_i \le 10^6, \, i = 1, 2, \ldots, n)$$$, $$$d_i$$$ — длительность работы лампочки, установленной в фонаре $$$\#i$$$.

В третьей строке содержится $$$s$$$ целых чисел $$$t_1, t_2, \ldots, t_s$$$ $$$(1 \le t_j \le 10^6, \, j = 1, 2, \ldots, s)$$$, $$$t_j$$$ — длительность работы лампочки, имеющей складской номер $$$\#j$$$.

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

Выведите три числа.

Первое число — номер дня, в который работникам парка придётся писать заявку (и они смогут отправиться в долгожданный отпуск).

Второе число — максимальное количество дней, которое пройдёт между двумя последовательными заменами лампочек в каком-либо одном фонаре.

Третье число — максимальное суммарное количество дней, которое какой-либо один фонарь будет оставаться неработающим.

Разделяйте числа пробелами или переводами строк.

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

Во подзадачах с первой по третью применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.

Баллы за четвёртую подзадачу начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.

В первой подзадаче лампочки, исходно установленные в фонарях, двух видов: с длительностью работы $$$a$$$ и с длительностью работы $$$b$$$. Все лампочки на складе имеют одну и ту же длительность работы $$$c$$$.

Во второй подзадаче все лампочки на складе имеют одну и ту же длительность работы $$$c$$$.

Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач.

Более подробно разбиение на подзадачи показано в таблице ниже.

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
11 (до 10)$$$s \le 1000, \, d_j \le 1000, \, t_i \le 1000 $$$нетполная
$$$d_j \in \{a, b\}, \, t_i = c$$$ для всех $$$j$$$, $$$i$$$
22 (до 30)$$$s \le 1000,\, d_j \le 1000, \, t_i \le 1000 $$$1полная
$$$t_i = c$$$ для всех $$$j$$$, $$$i$$$
32 (до 30)$$$s \le 1000,\, d_j \le 1000, \, t_i \le 1000 $$$1, 2полная
для всех $$$j$$$, $$$i$$$
4(30)любые возможные значения1, 2, 3первая ошибка

Примеры
Входные данные
3 3 2
7 4 7
8 4 6
Выходные данные
13
7
5
Входные данные
7 19 3
5 2 14 8 11 8 18
7 4 6 3 3 4 10 21 19 19 20 21 12 13 3 
5 4 4 5
Выходные данные
36
22
7
Примечание

Во втором примере (только в условии) часть данных из третьей строки перенесена на четвёртую строку, поскольку не помещалась в колонку таблицы. В тестирующей системе никаких переносов строк нет.

Поясним приведённые примеры.

В первом примере работники отправятся менять лампочки в день $$$7$$$. В день $$$4$$$ перегорит одна лампочка, но для них это не будет поводом делать замену (они планируют делать замены, если перегоревших лампочек не меньше $$$2$$$). В день $$$7$$$ перегорят ещё две лампочки, суммарное количество перегоревших станет равным $$$3$$$, и работники пойдут на склад.

На складе они обнаружат достаточное количество лампочек — $$$3$$$ штуки. Так что в день $$$7$$$ в первом фонаре будет установлена лампочка, которая проработает $$$8$$$ дней, во втором — лампочка, которая проработает $$$4$$$ дней, а в третьем — лампочка, которая проработает $$$6$$$ дней.

Это означает, что в день $$$11$$$ лампочка, установленная во втором фонаре, перегорит. Через два дня, в день $$$13$$$ перегорит лампочка в третьем фонаре. Перегоревших лампочек станет $$$2$$$, и работники отправятся на склад. Поскольку лампочек на складе не окажется, в день $$$13$$$ они составят заявку.

В период времени до дня $$$13$$$ замены лампочек производились в «нулевой» день, а затем в седьмой день — так что максимальное время прошедшее между двумя последовательными заменами составит $$$7$$$ дней.

Максимальное суммарное время, которое не работал какой-либо один фонарь, составляет $$$5$$$ дней для второго фонаря. Как легко видеть, первый и третий фонари до дня $$$13$$$ всегда были в работающем состоянии. А вот второй фонарь не работал сначала $$$3$$$ дня — c $$$4$$$ по $$$7$$$ день, а затем ещё $$$2$$$ дня — с $$$11$$$ по $$$13$$$ день. В условии предлагается ограничиться днём, в который была сформирована заявка на приобретение лампочек, поэтому о дальнейшей «истории» этого фонаря никаких предположений не делается.

Второй пример демонстрирует различные ситуации замен лампочек. Заметим, что значение $$$22$$$ (максимальное количество дней, прошедших между последовательными заменами лампочек) достигается для седьмого фонаря.

Максимальное суммарное количество дней, которое не работал какой-либо фонарь, составляет $$$7$$$ и достигается для второго и пятого фонарей.