WINMAXK - Maximum K in a Window

Note: The time limit is strict, so that only algorithms with complexity O(NM) will pass.

You are given an array of N positive integers.
We define the score of a continuous subarray of length K as the sum of its top M elements.
Your task is to find the L-th minimum score.

Input
In the first line, there are 4 positive integers, N K M L.
N lines follow. The i-th of them contain the i-th element of the array.
It holds that:

  • 1 ≤ N ≤ 106
  • 1 ≤ K ≤ N
  • 1 ≤ M ≤ 5
  • 1 ≤ L ≤ N-K+1
  • all elements are at most 260


Output
The L-th minimum score.

Example
    Input

    6 3 2 2
    7
    4
    3
    9
    2
    8


    Output
    12

    Explanation
    There are 4 different subarrays:
    [7 4 3] with score 7+4 = 11.
    [4 3 9] with score 4+9 = 13.
    [3 9 2] with score 3+9 = 12.
    [9 2 8] with score 9+8 = 17.
    The second minimum is 12.


Added by:kipoujr
Date:2018-06-26
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Original

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.