An SDE is planning focused deep work sessions for the next n days.
On day i, they can complete ai units of productive work.
They want to choose exactly k non-overlapping work sprints. Each sprint must be a contiguous group of days, and every chosen sprint must have length at least L.
The total productivity is the sum of ai over all days included in the chosen sprints.
Your task is to find the maximum possible value of L such that the SDE can choose exactly k valid sprints with total productivity at least T.
If it is impossible even for L = 1, print 0.
The first line contains three integers n, k, and T — the number of days, the number of work sprints, and the required total productivity.
The second line contains n integers a1, a2, ..., an — the productive work units for each day.
Print a single integer — the maximum sprint length L such that exactly k non-overlapping sprints of length at least L can achieve total productivity at least T.
Input
7 2 18
3 2 7 10 1 4 6Output
2Explanation
For
L = 2, one possible choice is:
- Sprint
[2, 4]with productivity2 + 7 + 10 = 19 - Sprint
[6, 7]with productivity4 + 6 = 10
The total productivity is
19 + 10 = 29, which is at least 18.
For
L = 3, it is not possible to choose exactly 2 non-overlapping sprints with total productivity at least 18.
Therefore, the maximum valid value of
L is 2.