Идет дождь.
Дождь состоит из $$$n$$$ капель, падающих вертикально вниз на прямую $$$y=0$$$. Для каждой капли известно положение, куда она упадет — $$$x_i$$$ и время, когда она упадет — $$$t_i$$$. После падения капля растекается так, что через $$$k$$$ секунд она полностью накроет отрезок $$$[x_i - k, x_i + k]$$$, включая его концы.
Вам нужно найти наименьшее целое число $$$T$$$, такое что через $$$T$$$ секунд капли полностью накроют отрезок $$$[0, r]$$$.
Первая строка содержит два натуральных числа $$$n$$$ — количество капель $$$(1 \leq n \leq 2\cdot 10^6)$$$ и $$$r$$$ — границу отрезка, который нужно накрыть $$$(1 \leq r \leq 10^9)$$$.
Во второй строке даны $$$n$$$ целых чисел $$$x_i$$$ — координаты капель $$$(0 \leq x_i \leq 10^9)$$$.
В третьей строке даны $$$n$$$ целых чисел $$$t_i$$$ — времена падения капель $$$(0 \leq t_i \leq 10^9)$$$.
Вывести одно целое число — минимальное количество секунд, через которое будет полностью накрыт отрезок $$$[0, r]$$$.
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий |
| $$$0$$$ | $$$0$$$ | — | — | Тесты из условия |
| $$$1$$$ | $$$20$$$ | $$$n, r, x_i, t_i \leq 100$$$ | — | Каждый тест |
| $$$2$$$ | $$$20$$$ | $$$n, r, x_i, t_i \leq 5000$$$ | — | Каждый тест |
| $$$3$$$ | $$$50$$$ | $$$n \leq 2\cdot 10^5$$$ | — | Каждый тест |
| $$$4$$$ | $$$10$$$ | — | — | Каждый тест |
3 5 1 3 5 1 3 3
4
4 2 3 2 1 0 1 1 1 1
2
1 7 2 0
5
В первом примере в секунды 0, 1, 2, 3, 4 будут получатся такие картинки (синие точки — капельки, зеленый отрезок — отрезок, который необходимо накрыть, синий отрезок — растекшиеся капельки):
Во втором примере получатся такие картинки:
