Problem: A top-secret military base under the command of Colonel Zuev is expecting an inspection from the Ministry of Defence. According to the charter, each top-secret military base must include a top-secret troop that should... well, we cannot tell you exactly what it should do, it is a top secret troop at the end. The problem is that Zuev's base is missing this top-secret troop for some reasons.

The colonel decided to deal with the problem immediately and ordered to line up in a single line all n soldiers of the base entrusted to him. Zuev knows that the loquacity of the i-th soldier from the left is equal to qi. Zuev wants to form the top-secret troop using k leftmost soldiers in the line, thus he wants their total loquacity to be as small as possible (as the troop should remain top-secret). To achieve this, he is going to choose a pair of consecutive soldiers and swap them. He intends to do so no more than s times. Note that any soldier can be a participant of such swaps for any number of times. The problem turned out to be unusual, and colonel Zuev asked you to help.

Determine, what is the minimum total loquacity of the first k soldiers in the line, that can be achieved by performing no more than s swaps of two consecutive soldiers.

Input

The first line of the input contains three positive integers n, k, s (1 ≤ k ≤ n ≤ 150, 1 ≤ s ≤ 109) — the number of soldiers in the line, the size of the top-secret troop to be formed and the maximum possible number of swap operations of the consecutive pair of soldiers, respectively.

The second line of the input contains n integer qi (1 ≤ qi ≤ 1 000 000) — the values of loquacity of soldiers in order they follow in line from left to right.

Output

Print a single integer — the minimum possible total loquacity of the top-secret troop.

Examples

Input

3 2 2
2 4 1


Output

3


Input

5 4 2
10 1 6 2 5


Output

18


Input

5 2 3
3 1 4 2 5


Output

3

Note

In the first sample Colonel has to swap second and third soldiers, he doesn't really need the remaining swap. The resulting soldiers order is: (2, 1, 4). Minimum possible summary loquacity of the secret troop is 3. In the second sample Colonel will perform swaps in the following order:

  1. (10, 1, 6 — 2, 5) 
  2. (10, 1, 2, 6 — 5) 



The resulting soldiers order is (10, 1, 2, 5, 6). 

Minimum possible summary loquacity is equal to 18.

Solution (in JAVA):

Solution:


import java.math.*;
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStream;  
import java.io.InputStreamReader;  
import java.math.BigInteger;  
import java.util.StringTokenizer;  
import java.io.PrintWriter;
import java.util.Arrays;
public class D {

    public static void main(String args[])  {
        scanner in = new scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

            int n = in.nextInt();
            int k = in.nextInt();
            int s = in.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n ; i++) {
                a[i] = in.nextInt();
            }

            // 入力に対して問題を解く
            out.println(solve(a, k, s));
            out.flush();
        }
    

    private static int solve(int[] a, int k, int s) {
        int n = a.length;
    
        // s が十分にある場合
        if (s >= n * (n - 1) / 2) {
            // 小さいのから k 個の和が答え
            Arrays.sort(a);
            int ret = 0;
            for (int i = 0; i < k ; i++) {
                ret += a[i];
            }
            return ret;
        }
    
        // dp[今何番目の数を見ているか][これまでに幾つ数を選んだか][先頭に動かす時のコストはいくつか] := 選んだ数の和はいくつか
        // そのまま (今何番目の数を見ているか) を持つとメモリが足りないので頑張って使い回す
        int[][][] dp = new int[2][k+1][s+1];
        for (int f = 0; f <= 1; f++) {
            for (int j = 0; j <= k; j++) {
                Arrays.fill(dp[f][j], Integer.MAX_VALUE);
            }
        }
        dp[0][0][0] = 0;
    
        for (int i = 0; i < n ; i++) {
            // fr,to は (0,1) と (1,0) のどれか。
            // dp[fr] := 計算元
            // dp[to] := 計算先
            // i が増える度に入れ替わるようにする
            int fr = i % 2;
            int to = 1 - fr;
    
            // 計算先を十分大きな値で埋める(こうしとかないと前回(i-2)の計算結果が入ってておかしなことになる)
            for (int j = 0; j <= k; j++) {
                Arrays.fill(dp[to][j], Integer.MAX_VALUE);
            }
    
            // j : 選んだ数値の数
            // l : 今までの移動回数
            for (int j = 0; j <= k; j++) {
                for (int l = 0; l <= s; l++) {
                    int base = dp[fr][j][l];
                    if (base == Integer.MAX_VALUE) {
                        continue;
                    }
    
                    // 数値 a[i] を採用する場合。左への移動回数は i-j (何故かは考えてみてください) で、
                    // これが累計 s を超えてなければ選べる
                    if (l+i-j <= s && j+1 <= k) {
                        // 選んだ数値の合計が小さいものを貪欲に選ぶ
                        dp[to][j+1][l+i-j] = Math.min(dp[to][j+1][l+i-j], base+a[i]);
                    }
    
                    // 数値 a[i] を採用しない場合。採用数、合計移動数、数値の合計共に変わらず
                    dp[to][j][l] = Math.min(dp[to][j][l], base);
                }
            }
        }
    
        // 答えの中から、一番小さいものを選ぶ
        int min = Integer.MAX_VALUE;
        for (int l = 0; l <= s ; l++) {
            min = Math.min(min, dp[n%2][k][l]);
        }
        return min;
    }
    static class scanner {  
        BufferedReader br;  
        StringTokenizer st;  
      
        public scanner(InputStream in) {  
            br = new BufferedReader(new InputStreamReader(in));  
            eat("");  
        }  
      
        private void eat(String s) {  
            st = new StringTokenizer(s);  
        }  
      
        public String nextLine() {  
            try {  
                return br.readLine();  
            } catch (IOException e) {  
                return null;  
            }  
        }  
      
        public boolean hasNext() {  
            while (!st.hasMoreTokens()) {  
                String s = nextLine();  
                if (s == null)  
                    return false;  
                eat(s);  
            }  
            return true;  
        }  
      
        public String next() {  
            hasNext();  
            return st.nextToken();  
        }  
      
        public int nextInt() {  
            return Integer.parseInt(next());  
        }  
      
        public long nextLong() {  
            return Long.parseLong(next());  
        }  
      
        public double nextDouble() {  
            return Double.parseDouble(next());  
        }  
      
        public BigInteger nextBigInteger() {  
            return new BigInteger(next());  
        }  
      
        public int[] nextIntArray(int n) {  
            int[] is = new int[n];  
            for (int i = 0; i < n; i++) {  
                is[i] = nextInt();  
            }  
            return is;  
        }  
      
        public long[] nextLongArray(int n) {  
            long[] ls = new long[n];  
            for (int i = 0; i < n; i++) {  
                ls[i] = nextLong();  
            }  
            return ls;  
        }  
      
        public double[] nextDoubleArray(int n) {  
            double[] ds = new double[n];  
            for (int i = 0; i < n; i++) {  
                ds[i] = nextDouble();  
            }  
            return ds;  
        }  
      
        public BigInteger[] nextBigIntegerArray(int n) {  
            BigInteger[] bs = new BigInteger[n];  
            for (int i = 0; i < n; i++) {  
                bs[i] = nextBigInteger();  
            }  
            return bs;  
        }  
      
        public int[][] nextIntMatrix(int row, int col) {  
            int[][] mat = new int[row][];  
            for (int i = 0; i < row; i++) {  
                mat[i] = nextIntArray(col);  
            }  
            return mat;  
        }  
      
        public long[][] nextLongMatrix(int row, int col) {  
            long[][] mat = new long[row][];  
            for (int i = 0; i < row; i++) {  
                mat[i] = nextLongArray(col);  
            }  
            return mat;  
        }  
      
        public double[][] nextDoubleMatrix(int row, int col) {  
            double[][] mat = new double[row][];  
            for (int i = 0; i < row; i++) {  
                mat[i] = nextDoubleArray(col);  
            }  
            return mat;  
        }  
      
        public BigInteger[][] nextBigIntegerMatrix(int row, int col) {  
            BigInteger[][] mat = new BigInteger[row][];  
            for (int i = 0; i < row; i++) {  
                mat[i] = nextBigIntegerArray(col);  
            }  
            return mat;  
        }  
    }  
}