Chọn bộ cảm biến không kề nhau

Bối cảnh và bài toán

Có n cảm biến xếp trên một tuyến, cảm biến i mang trọng số a[i]. Cần chọn đúng k cảm biến, nhưng hai cảm biến ở vị trí kề nhau không được cùng chọn. Tổng trọng số của các cảm biến được chọn phải nằm trong đoạn [L,R].

Yêu cầu

Đếm số cách chọn thỏa tất cả điều kiện.

Input

• Dòng 1: n k L R.
• Dòng 2: n số nguyên a[i].

Output

In số cấu hình hợp lệ.

Ràng buộc

• 1 <= n <= 22
• 1 <= k <= 10
• -10^9 <= a[i], L, R <= 10^9
• L <= R

Chấm điểm

Ví dụ 1

Input

4 2 3 10
1 2 3 4

Output

3

Giải thích. Các cặp không kề là (1,3), (1,4), (2,4), đều có tổng trong đoạn.

Ví dụ 2

Input

3 2 0 100
5 6 7

Output

1

Giải thích. Chỉ có thể chọn vị trí 1 và 3 vì vị trí kề nhau bị cấm.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.