There are n bulbs arranged in a row. The state of the bulbs is represented by a binary string bulbs of length n, the 0 at ith position in the string represents the bulb is OFF and 1 represents the bulb is ON, where 0≤i<n. You have to switch OFF all the bulbs by performing following operation atmost k times. The operation is defined as:-
The task is to find the smallest value of l greater than zero, such that you can turn OFF all the bulbs in atmost k operations.
Input format
Output format
The output contains a single integer, the minimum possible value of l greater than zero such that you are able to turn OFF all the bulbs in atmost k operations.
Constraints
1≤n≤1061≤k≤n
For l = 1, The operation can be perfomed by choosing following intervals
For l = 2, The operation can be perfomed by choosing following intervals
For l = 3, The operation can be perfomed by choosing following intervals
Hence the answer is 3.