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 ≤ 10⁶
• 1 ≤ K ≤ N
• 1 ≤ M ≤ 5
• 1 ≤ L ≤ N-K+1
• all elements are at most 2⁶⁰

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.