601. Sleeping Schedule

0

Medium

Vova has a unique sleeping pattern. Each day consists of h hours. Vova will sleep exactly n times. The i-th time he will sleep exactly after ai hours from the time he woke up. It is assumed that Vova woke up at the beginning of this story (the initial time is 0). Each time Vova sleeps for a duration of h hours.
Vova considers the i-th sleeping time to be good if he starts to sleep between hours l and r (inclusive).
Vova has control over his sleeping schedule and before each sleeping time, he can choose between two options: go to sleep after ai hours or after ai-1 hours.
Your task is to determine the maximum number of good sleeping times Vova can achieve if he acts optimally.

Input Format

The input consists of four integers: n, h, l, and r. n represents the number of times Vova goes to sleep, h represents the number of hours in a day, and l and r represent the segment of the good sleeping time.
The second line of the input contains n integers a1, a2, ..., an, where ai is the number of hours after which Vova goes to sleep for the i-th time.

Output Format

Print a single integer, which represents the maximum number of good sleeping times Vova can achieve if he acts optimally.

Example

Input

7 24 21 23
16 17 14 20 20 11 22

Output

3

Constraints

1≤n≤2000

3≤h≤2000

0≤l≤r
1≤ai

3≤h≤2000

0≤l≤r

Loading...

View Submissions

Console