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

Коту Бенедикту очень нравится число $$$k$$$ и он хочет стать $$$k$$$-мышовым котом.

Как известно, кот считается $$$k$$$-мышовым, если он в течение некоторого времени ловит не менее $$$k$$$ мышей. Известны последовательные моменты времени $$$(0 \le) \, t_1 \le t_2 \le \ldots \le t_n$$$, в которые кот Бенедикт ловил мышей. Для каждого момента $$$t_i$$$ также известно количество мышей $$$m_i$$$, которых кот поймал в этот момент.

Кот Бенедикт хотел бы продемонстрировать, что он способен поймать $$$k$$$ мышей за короткое время. Поэтому он хочет выбрать наиболее короткий отрезок времени из диапазона от $$$0$$$ до $$$t_n$$$ (включительно), в течение которого он поймал не менее $$$k$$$ мышей.

Ваша задача — указать границы такого временного отрезка минимальной длины, которые позволят считать кота Бенедикта $$$k$$$-мышовым. Если существует несколько вариантов ответа, выведите любой из них.

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

В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5,\, 1 \le k \le 10^{18})$$$ — количество моментов времени, в которые кот Бенедикт ловил мышей, а также число $$$k$$$.

Во второй строке содержатся целые числа $$$t_1, t_2, \ldots, t_n$$$ $$$\left(0 \le t_1 \le t_2 \le \ldots \le t_n \le 10^{18} \right)$$$ — моменты времени, в которые кот Бенедикт ловил мышей.

В третьей строке содержатся целые числа $$$m_1, m_2, \ldots, m_n$$$ $$$\left(1 \le m_j \le 10^{9}, \, j = 1, 2, \ldots, n \right)$$$, $$$m_j$$$ — количество мышей, которых кот Бенедикт поймал в момент $$$t_j$$$.

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

Выведите два целых числа — начальный и конечный моменты времени, ограничивающие временной отрезок минимальной длины, в течение которого кот Бенедикт поймал не менее $$$k$$$ мышей. Разделяйте числа пробелом или переводом строки.

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

Если кот Бенедикт не сможет стать $$$k$$$-мышовым котом, выведите в качестве ответа два числа: $$$-1$$$ $$$-1$$$.

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

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

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

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

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

ПодзадачаБаллы за тестОграниченияНеобходимыеИнформация
(баллыподзадачио проверке
за подзадачу)
12 (до 20)$$$n \le 1000, \, k \le 1000, $$$нетполная
$$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$
$$$m_j = 1 \, (j = 1, 2, \ldots, n)$$$
22 (до 20)$$$n \le 1000, \, k \le 10^9, $$$1полная
$$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$
$$$m_j \le 10^6 \, (j = 1, 2, \ldots, n)$$$
30 (20)$$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$1первая ошибка
$$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$
$$$ m_j = 1 \, (j = 1, 2, \ldots, n)$$$
40 (20)$$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$1, 2, 3первая ошибка
$$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$
$$$ m_j \le 5000 \, (j = 1, 2, \ldots, n)$$$
50 (20)любые возможные значения1, 2, 3, 4первая ошибка

Примеры
Входные данные
7 3
0 6 8 19 22 23 25
1 1 1 1 1 1 1
Выходные данные
22
25
Входные данные
11 7
5 8 8 14 23 37 42 42 55 64 71
2 1 2 1 4 3 2 2 5 6 2
Выходные данные
37
42
Входные данные
5 8
1 5 15 20 28
2 1 1 2 1
Выходные данные
-1
-1
Примечание

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

В первом примере кот ловит по одной мыши в каждый момент времени.

  • На то, чтобы поймать первых трёх мышей, кот потратит $$$8$$$ единиц времени (первую мышь он поймает в момент $$$0$$$, а третью — в момент $$$8$$$).
  • Если кот будет учитывать мышей со второй по четвёртую, то на их поимку уйдёт $$$13$$$ единиц времени.
  • Если кот будет учитывать мышей с третьей по пятую, то их он поймает за $$$14$$$ единиц времени.
  • Если кот будет учитывать мышей с четвёртой по шестую, то на их поимку будет потрачено $$$4$$$ единицы времени.
  • Наконец, если кот будет учитывать мышей с пятой по седьмую, то их он поймает за $$$3$$$ единицы времени.

Таким образом, кот может утверждать, что может стать $$$k$$$-мышовым котом за $$$3$$$ единицы времени.

Во втором примере минимальное время, которое потребуется коту — $$$5$$$ единиц времени: он поймает трёх мышей в момент $$$37$$$, а затем еще дважды по две мыши в момент $$$42$$$.

В третьем примере кот не сможет стать $$$k$$$-мышовым