Priya grows flowers for the Ganesh festival. Her garden is one long row of n plants. The list bloomDay says when each plant flowers: plant i has its flower open on day bloomDay[i], and on every day after that.
She wants to make m bouquets. One bouquet needs k flowers from k plants that stand side by side. One flower goes into only one bouquet.
Return the smallest number of days Priya has to wait so that she can make m bouquets. If she can never make them, return -1.
Examples
Example 1:
Input: bloomDay = [8,3,3,9,3,3,3], m = 2, k = 3
Output: 8
Explanation: On day 3, plants 1, 2, 4, 5 and 6 are open. Plants 4, 5 and 6 make one bouquet. Plants 1 and 2 are only two, so they are not enough.
On day 8, plants 0, 1 and 2 are open too, and they make the second bouquet.
Example 2:
Input: bloomDay = [2,2,2], m = 1, k = 4
Output: -1
Explanation: One bouquet needs 4 flowers from plants side by side, but the garden has only 3 plants.
Example 3:
Input: bloomDay = [6,2,9,2,2,9], m = 2, k = 2
Output: 6
Explanation: On day 2, only plants 3 and 4 are side by side, so there is 1 bouquet. On day 6, plants 0 and 1 are open too. They make the second bouquet.