Problem K
Handheld Fan
You won a small handheld fan at an office party. Unfortunately, the battery is not replaceable – it is fused to the circuitry and is not rechargeable. The company wants you to buy a new fan when the charge is depleted (Canada is really far behind with right-to-repair legislation). The fan’s battery can operate for exactly $W$ hours with its initial charge.
You want to attend an outdoor festival taking place over the Summer and will take your fan to stay cool during the festival. The festival does not permit reentry and only allows people to enter or leave at start of each hour, so your time spent there will be in the form of a sequence of consecutive hours. You also know the hourly forecast for the next few days during the Folksy Music Festival. For an hour with a forecasted temperature of $T$ degrees Celsius, you will operate the fan exactly a $T/30$-fraction of the time during that hour (i.e. $2 \cdot T$ minutes during the hour).
You decide that you will only attend the festival during a sequence of consecutive hours if at the start of each hour your fan’s initial charge at that hour guarantees it can operate for a $T/30$-fraction of the time during that hour. What is the longest period of time you can attend the festival?
Input
The first line of input contains two integers $N$ ($1 \leq N \leq 1,000$) and $W$ ($1 \leq W \leq 1,000$). The next line contains $N$ integers $t_1, t_2, \ldots , t_n$ ($0 \leq t_i \leq 30$) where $t_i$ is the forecasted temperature for the $i$’th hour of the festival.
Output
Output a single integer $m$ indicating the maximum number of consecutive hours you are able to attend the festival if you pick the first hour optimally, assuming the hourly temperature forecast is correct.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 2 29 15 16 18 30 28 17 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 0 30 30 30 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 3 1 30 30 30 |
3 |
| Sample Input 4 | Sample Output 4 |
|---|---|
4 3 30 30 30 0 |
4 |
