Xiao Ming is ACM's Dalao in the grade (this Xiao Ming is not That Xiaoming), and the classmates once asked Xiao Ming a question:
Give you a sequence A containing n integers, asking what is the value of the m-th largest interval sum? (interval and no de-duplication).
For example, A={1,2,3,4,4}, then Sum[2,5] = 2 + 3 + 4 + 4 = 13.
It is well known that n numbers have a total of n*(n+1)/2 intervals, and how many intervals have how many interval sum.
The arrogant Xiao Ming thinks that this question is too simple and does not want to answer. In order to suppress the arrogant Xiao Ming, the classmates added a rule to Xiao Ming:
The same number in the interval can only be calculated up to k times.
That is, for the above sequence A, when k=1, Sum[2,5] = 2 + 3 + 4 = 9. (At this time, the number 4 can only be calculated once)
Xiao Ming was beaten back to the original form, but he want to save his face and secretly came to you to help him solve this problem. Can you help him?
这题还是不会翻译
The first line have three integer n, m, k.
The second line of n numbers represents the n integers of sequence A.
(1<=n, k<=1e5. 1<=m<=min(1e5, n*(n+1)/2). |a[i]| <= 1e9)
Outputs a line of integers representing the value of the m-th largest interval sum.
10 6 2 2 2 2 -2 -2 -2 1 1 1 -1
2