[ADS] SpecialChoice ???

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class SpecialChoice {
    /*
    Дадени се N броеви и уште два броеви M и K.
    Да се изберат точно K броеви од низата за кои важи дека два последователни броеви немаат збир поголем од M и
    вкупната сума на сите избрани броеви треба да биде максимална. Да се испечати оваа сума.
    Забелешка: секогаш ќе постои оптимално решение.

    Влез: Во првата линија ви се дадени три броеви N (1≤N≤100), M (1≤M≤2,000) и K (1≤K≤100, K≤N).
    Во втората линија ви се дадени N позитивни природни броеви, секој од броевите е помал од 1,000.

    Излез: Да се испечати бараната максимална сума.

    Sample input
    10 5 3
    1 9 2 3 6 1 3 2 1 3
    Sample output
    8
    */
    static int solve(int numbers[], int len, int upperlimit, int choose) {
        int matrix[][] = new int[len][choose + 1];
        int result = 0;

        final int UNDEFINED = 0;
        /* Make matrix undefined */
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < choose + 1; j++) {
                matrix[i][j] = UNDEFINED;
            }
        }

        /* Initialize matrix column 1 to be same as array*/
        for (int i = 0; i < len; i++) {
            matrix[i][1] = numbers[i];
        }

        /* i = 1, sum of 0 elements is 0 and sum of 1 elements is the element itself */
        for (int i = 1; i < len; i++) {
            for (int j = 2; j < choose + 1; j++) {
                for (int k = 0; k < i; k++) {
                    if (matrix[i][j] == UNDEFINED) {
                        if (numbers[k] + numbers[i] <= upperlimit) {
                            matrix[i][j] = matrix[k][j - 1] + numbers[i];
                        }
                    } else if (matrix[i][j] != UNDEFINED) {
                        /* Meaning it is defined */
                        /* current vs previous */
                        if (matrix[k][j - 1] != UNDEFINED) {
                            if (numbers[k] + numbers[i] <= upperlimit) {
                                matrix[i][j] = Math.max(matrix[i][j], matrix[k][j - 1] + numbers[k]);
                            }
                        }
                    }

                }
                result = Math.max(result, matrix[i][j]);
            }
        }


        /* Print Matrix */
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.print("\n");
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        /*int i,j,k;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int numbers[] = new int[N];

        st = new StringTokenizer(br.readLine());
        for (i=0;i<N;i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int res = solve(numbers, N, M, K);
        System.out.println(res);

        br.close();*/
        int N = 10;
        int M = 5;
        int K = 3;
        int numbers[] = {1, 9, 2, 3, 6, 1, 3, 2, 1, 3};
        int res = solve(numbers, N, M, K);
        System.out.println("RESULT " + res);
    }

}