CF550B.Preparing Olympiad

You have n problems. You have estimated the difficulty of the i-th one as integer c__i. Now you want to prepare a problemset for a contest, using some of the problems you've made.

A problemset for the contest must consist of at least two problems. You think that the total difficulty of the problems of the contest must be at least l and at most r. Also, you think that the difference between difficulties of the easiest and the hardest of the chosen problems must be at least x.

Find the number of ways to choose a problemset for the contest.

你有 $n$ 道题目。你已将第 $i$ 道题的难度估计为整数 $c_i$。现在你想从自己制作的题目中选出一部分，来准备一场竞赛的题目集。

一场竞赛的题目集必须包含至少两道题。你认为所选题目的总难度必须至少为 $l$，且至多为 $r$。此外，你还要求所选题目中最难题目与最简单题目的难度之差至少为 $x$。

求满足上述条件的题目集的选取方案数。

The first line contains four integers n, l, r, x (1 ≤ n ≤ 15, 1 ≤ l ≤ r ≤ 109, 1 ≤ x ≤ 106) — the number of problems you have, the minimum and maximum value of total difficulty of the problemset and the minimum difference in difficulty between the hardest problem in the pack and the easiest one, respectively.

The second line contains n integers _c_1, _c_2, ..., c__n (1 ≤ c__i ≤ 106) — the difficulty of each problem.

第一行包含四个整数 $n$、$l$、$r$、$x$（$1 ≤ n ≤ 15$，$1 ≤ l ≤ r ≤ 10^9$，$1 ≤ x ≤ 10^6$）—— 分别表示你拥有的题目数量、题集总难度的最小值与最大值，以及题集中最难题目与最简单题目之间难度的最小差值。

第二行包含 $n$ 个整数 $c_1,\,c_2,\,...,\,c_n$（$1 ≤ c_i ≤ 10^6$）—— 表示每道题的难度。

Print the number of ways to choose a suitable problemset for the contest.

输出为比赛选择合适题目集的方法数。

In the first example two sets are suitable, one consisting of the second and third problem, another one consisting of all three problems.

In the second example, two sets of problems are suitable — the set of problems with difficulties 10 and 30 as well as the set of problems with difficulties 20 and 30.

In the third example any set consisting of one problem of difficulty 10 and one problem of difficulty 20 is suitable.

在第一个例子中，有两个合适的集合：一个包含第二个和第三个问题，另一个包含全部三个问题。

在第二个例子中，有两个合适的问题集合：一个是难度为 10 和 30 的问题集合，另一个是难度为 20 和 30 的问题集合。

在第三个例子中，任意一个由一道难度为 10 的问题和一道难度为 20 的问题组成的集合都是合适的。