public static int backPack(int m, ArrayList<Integer> A){
		
		// write your code here
		
        boolean[][] matrix = new boolean[A.size() + 1][m + 1];
        matrix[0][0] = true;
        for (int i = 1; i < m; i++){
            matrix[0][i] = false;
        }
        for (int i = 1; i <= A.size(); i++){
            for (int j = 0; j <= m; j++){
            	for (int k = 1; k <= i; k++){
            		if (j - A.get(i - k) < 0){
            			matrix[i][j] = matrix[i - k][j];
            		} else {
            			matrix[i][j] = matrix[i - k][j - A.get(i - k)];
            		}
            		if (matrix[i][j])
            			break;
            	}

            }
        }
        
        
        
        int max = 0;
        for (int i = m ; i >=0; i--){
            if (matrix[A.size()][i]){
                max = Math.max(max, i);
                break;
            }
        }
        return max;
	}