Chọn Bộ Bài Cân Đối · canuc80k0713

Có $n$ bài, bài $i$ có độ khó $c_{i}$ . Chọn một tập gồm ít nhất hai bài sao cho tổng độ khó nằm trong đoạn $[l, r]$ và hiệu giữa độ khó lớn nhất với nhỏ nhất trong tập không nhỏ hơn $x$ . Hãy đếm số tập thỏa mãn.

Input

Dòng đầu chứa bốn số $n$ $l$ $r$ $x$ . Dòng thứ hai chứa $n$ số $c_{1}, \dots, c_{n}$ .

Output

In số tập bài hợp lệ.

Constraints

$1 \leq n \leq 15$ .
$1 \leq l \leq r \leq 1 0^{9}$ .
$1 \leq x \leq 1 0^{6}$ .
$1 \leq c_{i} \leq 1 0^{6}$ .

Scoring

Subtask $1$ ( $50%$ ): $n \leq 10$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

5 21 61 19
1 10 20 30 40

Output

Giải thích: Tập ${1, 20}$ có tổng $21$ và độ chênh $19$ , nên hợp lệ; các tập khác được kiểm tra theo cùng ba điều kiện. Kết quả là tổng số tập con đạt đồng thời mọi điều kiện.

Ý tưởng: Mỗi bài có hai khả năng: chọn hoặc bỏ. Trạng thái cần đủ bốn thống kê của tập đang xây: số phần tử, tổng, nhỏ nhất và lớn nhất.
Thuật toán: Đệ quy theo chỉ số bài. Nhánh thứ nhất bỏ bài hiện tại; nhánh thứ hai chọn nó và cập nhật các thống kê. Khi đã xét hết n bài, tăng đáp án nếu tập có ít nhất hai phần tử, tổng thuộc [l,r] và hiệu lớn nhất-nhỏ nhất không nhỏ hơn x. Vì mọi độ khó dương, có thể dừng sớm khi tổng đã vượt r.
Tính đúng đắn: Mỗi tập con có đúng một dãy quyết định chọn/bỏ, nên cây duyệt mọi tập đúng một lần. Các thống kê được cập nhật theo định nghĩa và vì thế tại lá chính là thống kê của tập đã chọn. Điều kiện ở lá trùng với ba điều kiện đề bài, do đó số lá được đếm là đáp án.
Độ phức tạp: Thời gian O(2^n) và bộ nhớ ngăn xếp O(n).