Maximum Rest

Interview

Time limit2sMemory limit1024 MB

Summary

Choose workdays, each capped at W_i, so total work reaches M while the smallest gap between chosen workdays is as large as possible.

Level: Medium6 of 10
Topics: Binary search, Dynamic programming, Sliding window
Solved: No attempts yet

Problem

Amel is known as the most capable employee at the SKH company. However, Amel has very poor stamina and tires quickly after a day of work, so Amel wants to rest for as long as possible after each stretch of work. On day $i$ , Amel can work at most $W_i$ , and Amel must complete a total of $M$ units of work. Amel wants to maximize the minimum length of the consecutive rest periods between working days.

For example, suppose the workloads for 7 days are $1,\ 3,\ 5,\ 4,\ 3,\ 7,\ 3$ and the quota is $9$ . If Amel works on days 1, 3, and 7, then $1+5+3=9$ fills the quota. The rest periods are 1 day and 3 days, so the minimum is 1 day. If Amel works on days 2 and 6, then $3+7=10$ fills the quota, and the rest period is 3 days, so the minimum is 3 days. If Amel works on days 6 and 7, the gap between working days is 0 days, so the minimum is 0.

Rest before the first workday or after the last workday is not counted as a rest period.

Input

The first line contains the number of days $N$ ( $2 \leq N \leq 2 \times 10^5$ ) and the quota $M$ ( $1 \leq M \leq 10^8$ ), separated by a space.

The second line contains $W_i$ ( $1 \leq i \leq N$ , $1 \leq W_i \leq 10^7$ ), the maximum amount of work Amel can do on day $i$ , separated by spaces.

All input values are integers.

Output

Print the maximum possible value of the minimum length of consecutive rest periods.

If Amel cannot fill the quota even by working all $N$ days, print -1. If the quota can be filled in one day, print "Free!" (without the quotes).

Examples4

Example 1
Input
```
7 9
1 3 5 4 3 7 3
```
Expected output
```
3
```
Example 2
Input
```
5 5
1 2 3 4 5
```
Expected output
```
Free!
```
Example 3
Input
```
5 20
1 2 3 4 5
```
Expected output
```
-1
```
Example 4
Input
```
11 20
1 5 2 8 4 7 2 9 8 2 8
```
Expected output
```
3
```