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

У Вовы довольно странный режим сна. В сутках $$$h$$$ часов. Вова будет спать ровно $$$n$$$ раз. В $$$i$$$-й раз он будет спать ровно после $$$a_i$$$ часов после пробуждения. Предположим, что Вова просыпается ровно в начале этой истории (изначальное время равно $$$0$$$). Каждый раз Вова спит ровно сутки (другими словами, $$$h$$$ часов).

Вова думает, что $$$i$$$-й раз, когда он спит, — хороший, если он идет спать между $$$l$$$ и $$$r$$$ часами включительно.

Вова может контролировать себя и перед $$$i$$$-м разом он может выбрать одно из двух: пойти спать после $$$a_i$$$ часов или после $$$a_i - 1$$$ часов.

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

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

Первая строка теста содержит четыре целых числа $$$n, h, l$$$ и $$$r$$$ ($$$1 \le n \le 2000, 3 \le h \le 2000, 0 \le l \le r < h$$$) — количество раз, которое Вова будет спать, количество часов в сутках и отрезок хорошего времени для сна.

Вторая строка теста содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i < h$$$), где $$$a_i$$$ — количество часов, после которого Вова пойдет спать в $$$i$$$-й раз.

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

Выведите одно целое число — максимальное количество хороших раз, которое Вова может получить, если будет действовать оптимально.

Пример
Входные данные
7 24 21 23
16 17 14 20 20 11 22
Выходные данные
3
Примечание

Максимальное количество хороших раз в тестовом примере равно $$$3$$$.

История начинается с $$$t=0$$$. Затем Вова идет спать после $$$a_1 - 1$$$ часов, теперь время равно $$$15$$$. Это время не является хорошим. Затем Вова идет спать после $$$a_2 - 1$$$ часов, теперь время равно $$$15 + 16 = 7$$$. Это время также не является хорошим. Затем Вова идет спать после $$$a_3$$$ часов, теперь время равно $$$7 + 14 = 21$$$. Это время является хорошим. Затем Вова идет спать после $$$a_4 - 1$$$ часов, теперь время равно $$$21 + 19 = 16$$$. Это время не является хорошим. Затем Вова идет спать после $$$a_5$$$ часов, теперь время равно $$$16 + 20 = 12$$$. Это время не является хорошим. Затем Вова идет спать после $$$a_6$$$ часов, Теперь время равно $$$12 + 11 = 23$$$. Это время является хорошим. Затем Вова идет спать после $$$a_7$$$ часов, теперь время равно $$$23 + 22 = 21$$$. Это время также является хорошим.