Optimal Sleep Schedule

You are planning your sleep schedule for N consecutive days. The day has h hours, numbered 0 to h-1. For each day i (from 0 to N-1), you are given a required sleep duration a[i].

The process is as follows:

Your schedule starts on the morning of day 0, at hour 0.

On each day i, you begin your "sleep session" at the hour you woke up on that same day.

For your sleep session, you have two choices:

Sleep for exactly a[i] hours.

Sleep for a[i] - 1 hours.

Your wake-up time for the next day (i+1) is calculated as (starttime + sleepduration) % h.

There is a "good" interval of hours to wake up, from hour l to r inclusive. Your goal is to make a sequence of sleep duration choices to maximize the total number of times you wake up within this good interval.

Input Format:

The first line contains four space-separated integers: n, h, l, and r.

The second line contains n space-separated integers, representing the sleep durations a[0], a[1], ....

Output Format:

Print a single integer representing the maximum possible number of good wake-ups.

Note:

This problem has optimal substructure and overlapping subproblems, making it a perfect fit for Dynamic Programming.