Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

B. Подготовка олимпиады
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть n задач. Сложность i-й из них вы оценили целым числом ci. Теперь вы хотите подготовить комплект задач для олимпиады, используя некоторые из придуманных задач.

Комплект задач для олимпиады должен состоять не менее чем из двух задач. Вы считаете, что суммарная сложность задач олимпиады должна быть не менее l и не более r. Также вы считаете, что разница в сложности между самой легкой и самой тяжелой из выбранных задач должна быть не меньше x.

Найдите количество способов выбрать комплект задач для олимпиады.

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

Первая строка содержит четыре целых числа n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) — соответственно количество задач в вашем распоряжении, минимальное и максимальное значение суммарной сложности комплекта задач и минимальная разница по сложности между самой сложной задачей в комплекте и самой лёгкой.

Вторая строка содержит n целых чисел c1, c2, ..., cn (1 ≤ ci ≤ 106) — сложность каждой из придуманных задач.

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

Выведите количество способов выбрать подходящий комплект задач для олимпиады.

Примеры
Входные данные
3 5 6 1
1 2 3
Выходные данные
2
Входные данные
4 40 50 10
10 20 30 25
Выходные данные
2
Входные данные
5 25 35 10
10 10 20 10 20
Выходные данные
6
Примечание

В первом примере подходят два комплекта: состоящий из второй и третьей задачи, а также состоящий из всех трех задач.

Во втором примере подходят два комплекта задач — комплект из задач сложностями 10 и 30, а также комплект из задач сложностями 20 и 30.

В третьем примере подходит любой комплект, в котором одна задача имеет сложность 10, а вторая — сложность 20.