Гриша пишет дипломную работу на тему автостоянок в Берляндии. В ходе дипломной работы ему потребовалось решать следующую задачу.
Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.
Требуется поставить на стоянку еще одну машину, которая приехала из другой страны. Причем машина не должна выходить за границы стоянки и пересекаться с другими машинами. Гриша хочет выяснить, какую наибольшую длину может иметь приехавшая машина, чтобы ее можно было поставить между любыми двумя смежными машинами, либо между стеной и машиной. Причем машину поставить на стоянку не так просто, поэтому слева и справа расстояние от границ приехавшей машины до ближайшего препятствия (другой машины или стены) должно быть не меньше некоторого b.
С учетом этих требований найдите наибольшую длину автомобиля, который можно поставить на стоянку.
Входные данные
В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.
В следующей строке находятся
n неотрицательных чисел
Xi (
Xi <
M) — точки, в которых располагаются левые границы машин.
Гарантируется, что машины не пересекаются между собой, а также со стенами, но возможно соприкасаются.
Выходные данные
Первая строка должна содержать число L — максимально возможную длину автомобиля, который можно поставить на стоянку с учетом вышеизложенных требований.
Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.
Пример входных и выходных данных
| Ввод |
Вывод |
Примечание |
4 21 1 1
7 12 3 16 |
1 |
|
4 30 3 1
24 5 11 18 |
1 |
|
2 20 3 1
7 10 |
0 |
В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину. |