D. Черные клетки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете с очень длинной полоской, состоящей из $$$10^{18}$$$ белых клеток и пронумерованной слева направо числами $$$0$$$, $$$1$$$, $$$2$$$ и так далее. Вы управляете особым указателем, который первоначально указывает на клетку $$$0$$$. Также у вас есть кнопка «Shift», которую вы можете зажимать.

За один шаг, вы можете сделать одно из трех действий:

  • сдвинуть указатель вправо (из клетки $$$x$$$ в клетку $$$x + 1$$$);
  • нажать и держать кнопку «Shift»;
  • отпустить кнопку «Shift»: в момент, когда вы отпустите Shift, все клетки, которые были посещены с зажатым Shift, будут покрашены в черный.
(Конечно же, вы не можете нажать на уже зажатый Shift. Аналогично, вы не можете отпустить уже отпущенный Shift.)

Ваша задача — покрасить хотя бы $$$k$$$ клеток, но есть ограничение: вам заданы $$$n$$$ отрезков $$$[l_i, r_i]$$$ — вы можете красить только клетки, которые принадлежат этим отрезкам, т. е. вы можете покрасить клетку $$$x$$$ только если $$$l_i \le x \le r_i$$$ для некоторого $$$i$$$.

Какое наименьшее количество шагов вам нужно выполнить, чтобы покрасить хотя бы $$$k$$$ клеток в черный?

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора заданы два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — количество отрезков и желаемое количество черных клеток.

Во второй строке заданы $$$n$$$ целых чисел $$$l_1, l_2, \dots, l_n$$$ ($$$1 \le l_1 < l_2 < \dots < l_n \le 10^9$$$), где $$$l_i$$$ — это левая граница $$$i$$$-го отрезка.

В третьей строке заданы $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 10^9$$$; $$$l_i \le r_i < l_{i + 1} - 1$$$), где $$$r_i$$$ — это правая граница $$$i$$$-го отрезка.

Дополнительные ограничения на входные данные:

  • каждая клетка принадлежит не более чем одному отрезку;
  • сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите наименьшее количество шагов, необходимых для покраски хотя бы $$$k$$$ клеток в черный, или $$$-1$$$, если это невозможно.

Пример
Входные данные
4
2 3
1 3
1 4
4 20
10 13 16 19
11 14 17 20
2 3
1 3
1 10
2 4
99 999999999
100 1000000000
Выходные данные
8
-1
7
1000000004
Примечание

В первом наборе входных данных, одна из оптимальных стратегий — следующая:

  1. Сдвинуть вправо: указатель сдвигается в ячейку $$$1$$$;
  2. Зажать Shift;
  3. Отпустить Shift: клетка $$$1$$$ покрасится в черный;
  4. Сдвинуть вправо: указатель сдвигается в ячейку $$$2$$$;
  5. Сдвинуть вправо: указатель сдвигается в ячейку $$$3$$$;
  6. Зажать Shift;
  7. Сдвинуть вправо: указатель сдвигается в ячейку $$$4$$$;
  8. Отпустить Shift: клетки $$$3$$$ и $$$4$$$ покрасятся в черный.
Мы покрасили $$$3$$$ клетки за $$$8$$$ шагов.

Во втором наборе входных данных, мы можем покрасить только $$$8$$$ клеток, а нам нужно покрасить $$$20$$$ клеток.

В третьем наборе, одна из оптимальных стратегий — следующая:

  1. Сдвинуть вправо: указатель сдвигается в ячейку $$$1$$$;
  2. Сдвинуть вправо: указатель сдвигается в ячейку $$$2$$$;
  3. Сдвинуть вправо: указатель сдвигается в ячейку $$$3$$$;
  4. Зажать Shift;
  5. Сдвинуть вправо: указатель сдвигается в ячейку $$$4$$$;
  6. Сдвинуть вправо: указатель сдвигается в ячейку $$$5$$$;
  7. Отпустить Shift: клетки $$$3$$$, $$$4$$$ и $$$5$$$ покрасятся в черный.
Мы покрасили $$$3$$$ клетки за $$$7$$$ шагов.