import java.math.*;
import java.util.*;

class Direction
{
    static int newSetSize;
    static int counter;
    StringJoiner sj1 = new StringJoiner(",");
    static String coinsCollectedinAllMoves;
    static int [] maximumCoins = new int [5000];
    static String [] storeMinimumCoins = new String [newSetSize+1];
    static String [] storeMaximumCoins = new String [newSetSize+1];
    
    static int min;
    static int max;
    
    static int totalCoins;
    
    static int RIGHTvalue; 
    
    static int DOWNvalue;
    
    String valuesSet;
    
    static int currentPosX;
    
    static int currentPosY;
    
    static boolean successfulFinish=true;
    
    static int FirstCoinDownMove;
    static int FirstCoinRightMove;
    static int CoinsOnLastPositionMove; 
    
    static String alternatingDownRight = "Alternating DOWN => RIGHT => DOWN .......";
    static String alternatingRightDown = "Alternating RIGHT => DOWN => RIGHT.......";
    
    static String[] completedPaths = new String [1000];
 
    static int count;
    
    static String [] numbers;
    
    static boolean outBounds=false;
    
    static int[][] matrix;
    
    enum Directions
    {
        DOWN(DOWNvalue), RIGHT(RIGHTvalue);
            
        int size;
            
        Directions(int size)
        {
            this.size=size;
                
        }
    }
    
    
    public Direction(String valuesSet, int[][] matrix, String alternateDownRight, int newSetSize)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        this.newSetSize=newSetSize;
        
        movesAlternateDownRight();
    }
    
 
    public Direction(String valuesSet, String alternateRightDown, int[][] matrix, int newSetSize)
    {
        this.valuesSet=valuesSet;
        this.matrix=matrix;
        this.newSetSize=newSetSize;
        movesAlternateRightDown();
    }
    
    public void decision(String movementPattern, String coinsCollectedinAllMoves)
    {
        System.out.println("********DECISION!!!*****************");
        System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
        System.out.println("************************************");
            
        successfulFinish=false;
       
        if (currentPosY==(matrix.length-1) && currentPosX==(matrix[0].length-1))
        {
            successfulFinish=true;
            System.out.println("*****Successful: " + valuesSet);
                
            completedPaths[count] = (valuesSet +  "    Subset: " + count + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + totalCoins + " " + "("+movementPattern+")");
                
            maximumCoins[count] = totalCoins;
                
            getMinimumMaximumCoins();
                
            System.out.println("Stored total coins: " + maximumCoins[count]);
            count++;
        }
            
        currentPosX=0; 
        currentPosY=0;  
            
        if (!successfulFinish)
        {
            totalCoins=0;
                
        }
        
        sj1 = new StringJoiner(",");
            
        coinsCollectedinAllMoves=" ";
    }
    
    //THIS HAS WHOLE BEEN REMOVED AS PER ERRORS
    
//****************************************************************************************
    //public static void getMinimumMaximumCoins()
    //{
        
        //both minimum and maximum are the first item..
        //System.out.println("min:" + maximumCoins[0]);
        
        //this array maximumCoins has all the values for coins collected during execution.
        //System.out.println("max:" + maximumCoins[0]);
        
      //  max=maximumCoins[0];
        
        //since minimumCoins is currently empty when it reaches here first time, it will take first value
        //from maximumCoins.
    //    min=maximumCoins[0];
        
        //System.out.println("*******MINIMUM AND MAXIMUM OF ALL THE COINS COLLECTED  [Start Position => End Position]******");
    
        //this will store minimum turns...
        //also will store maximum turns..
        //Reason for separate arrays is since there can be 
        //multiple paths. Note question only seeks maximumCoins on path..
        //storeMinimumCoins = new String[1000];
        //storeMaximumCoins = new String[1000];
        
        //checking all values in array
        //for (int val: maximumCoins)
        //{
            //can no longer use this for validation.
            //Since unlike Snakes and Ladders, there can be a minimum route of 0
            // i.e no coins on entire path!!
            //also we know the entire set will constitute a valid entry inputted as part of the
            //start => end on the matrix... So there is no need to worry about any entries
            //being 0 (default value of integer array) for  int [] minimumCoins = new int [newSetSize];
            
            //CAREFUL
            //if (val!=0)
            //{
                //need index here. otherwise val already minimum will loop...
                //it doesnt need to compare  maximumCoins[0] with itself
                //since it is already stored in storeMaximumCoins[0].
                //if counter condition was not included, val==min
                //it would think that another minimum is found with same minimum
                //number of Coins.   And create a fresh entry in storeMinimumCoins. 
                
                //counter will be zero first time it reaches here...
                //so it will skil this...
                //if (val==min/* && counter!=0*/)  
            //{
                //when this method runs second time around, counter will be 1 since it is assigned below..
                //A reminder that maximumCoins keeps track of all coins collected in successful (START => END)
                
                //it will count from index 1 to length of  array containing all the coin totals....
                
                //if (counter<maximumCoins.length)
                //{
                    //System.out.println("value of counter: " + counter);
                    
                //on the code above,  maximumCoins[0], corresponds to completedPaths[0]
                        // .......    maximumCoins[maximumCoins.length-1] corresponds to  completedPaths [maximumCoins.length-1]            
                //so we can take all the entries from completedPaths in which  the coin total is equal
                //to existing minimum value
                //storeMinimumCoins[counter]=Direction.completedPaths[counter];
                //System.out.println("Stored as joint minimum: " + Direction.completedPaths[counter]);
                //}
            //}
            
            //need index here. otherwise val already minimum will loop...
            //same rationale above, but for maximum value...
                //if (val==max /*&& counter!=0*/)
            //{
                // need to have a think to ensure if this will go ArrayIndexOutOfBoundsException
                 //if it was processing     maximumCoins with 10 entries...
                 //maximumCoins.length would be 10
                 // in indexing,  it would run from  0 to 9
                 // the logic below reads  0<10   on first execution...  ( 10 executions from 0-9)
                 
                 //it doesn't matter if the 
                 
                //if (counter<maximumCoins.length)
                //{
                 //same rationale as above...
                //storeMaximumCoins[counter]=Direction.completedPaths[counter];
                //System.out.println("Stored as joint maximum: " + Direction.completedPaths[counter]);
                    
                //}
            //}
                
            //if it is a new minimum value
            //default counter value is 1...
            //again, similar principle as above. It prevents comparing against each other...
            //on this situation, I do not think it matters, since val<min  should not be true
            //for minimumCoins[0]<minimumCoins[0]
            //if (val<min /*&& counter!=1*/)
            //{
               // min=val;
                
                //erase contents of the store...
                //storeMinimumCoins = new String[newSetSize];
                
                //sets a new minimum
                //storeMinimumCoins[0]=Direction.completedPaths[counter];
                //System.out.println("Stored as new minimum: " + Direction.completedPaths[counter]);
            //}
            
            //same rationale as above.
            //if (val>max /*&& counter!=1*/)
            //{
                //max=val;
                
                //storeMaximumCoins = new String[newSetSize];
                
                //storeMaximumCoins[0]=Direction.completedPaths[counter];
                //System.out.println("Stored as new maximum: " + Direction.completedPaths[counter]);
            //}
            
            
            //posProcessed++;
        //}
        
        //}
        //counter++;
        //System.out.println("Minimum Coins is: " +  min);
        //System.out.println("Maximum Coins is: " +  max);
        
    //}
//****************************************************************************************


    //***********CHATGPT HAD TO WRITE ABOVE METHOD AGAIN********************    
    //3. Proposed fix for maximumCoins
    //You need to loop with proper indexing instead of relying on counter. For example:
    //Changes made:
    //•	Loop uses i from 0 to count-1 to match entries in maximumCoins and completedPaths.
    //•	minIndex and maxIndex track positions in storeMinimumCoins and storeMaximumCoins.
    //•	Eliminates dependency on counter, which was misaligned.
    public static void getMinimumMaximumCoins()
    {
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
    
        storeMinimumCoins = new String[1000];
        storeMaximumCoins = new String[1000];
    
        int minIndex = 0;
        int maxIndex = 0;
    
        for (int i = 0; i < count; i++)  // use count of successful paths
        {
            int val = maximumCoins[i];
            
            if (val > max)
            {
                max = val;
                storeMaximumCoins[0] = completedPaths[i];
                maxIndex = 1;
            }
            else if (val == max)
            {
                storeMaximumCoins[maxIndex] = completedPaths[i];
                maxIndex++;
            }
            if (val < min)
            {
                min = val;
                storeMinimumCoins[0] = completedPaths[i];
                minIndex = 1;
            }
            else if (val == min)
            {
                storeMinimumCoins[minIndex] = completedPaths[i];
                minIndex++;
            }
        }
    
        System.out.println("Minimum Coins is: " + min);
        System.out.println("Maximum Coins is: " + max);
    }
    //************************************************************************************** 

    public static void finalResults()
    {
         
        System.out.println("\n\n\nMinimum Coins is: " +  min);
        
        for (String s: storeMinimumCoins)
        {
            if (s!=null)
            {
                System.out.println(s);
            }
        }
        
        System.out.println("\nMaximum Coins is: " +  max);
        
        for (String s: storeMaximumCoins)
        {
            if (s!=null)
            {
                System.out.println(s);
            }
        }
        
        counter=0; 
        System.out.println("\n\n");
    }
    
    public void movesDown(int t, String movementPattern)
    {
        DOWNvalue = Integer.valueOf(numbers[t]);
                    
        System.out.println("Performing this movement: " + "(" + Directions.DOWN + "):  " + DOWNvalue);
                    
        if (currentPosY + DOWNvalue >=matrix.length)
        {
            System.out.println("MOVEMENT IS OUT OF BOUNDS");
            successfulFinish=false;
            outBounds=true;
            decision(movementPattern, sj1.toString());
        }
                    
        if (!outBounds)
        {
            if (t==0)
            {
                FirstCoinDownMove = matrix[currentPosY][currentPosX];
                sj1.add(Integer.toString(FirstCoinDownMove));
            }
            
            for (int i=1; i<=DOWNvalue; i++)
            {
                totalCoins = totalCoins + matrix[currentPosY+i][currentPosX];
                            
                sj1.add( Integer.toString(matrix[currentPosY+i][currentPosX]));
                
            }
        }
        
        totalCoins = totalCoins + FirstCoinDownMove;
                     
        FirstCoinDownMove=0;
        CoinsOnLastPositionMove=0;
                    
        coinsCollectedinAllMoves=sj1.toString();
        
        if (currentPosY + DOWNvalue <matrix.length && successfulFinish)
        {
            System.out.println("Successfully moved " + DOWNvalue + " downwards");
                       
            currentPosY = currentPosY +  DOWNvalue;
                       
            if ((t==numbers.length-1))
            {
                decision(movementPattern, sj1.toString());
            }
        }
    }
    
    public void movesRight(int t, String movementPattern)
    {
        RIGHTvalue=Integer.valueOf(numbers[t]);
                    
        System.out.println("Performing this movement: " + "(" + Directions.RIGHT + "):  " + RIGHTvalue);
        
        if (currentPosX + RIGHTvalue >=matrix[0].length)
        {
            System.out.println("MOVEMENT IS OUT OF BOUNDS");
            successfulFinish=false;
            outBounds=true;
            decision(movementPattern, sj1.toString());
        }
                   
        if (!outBounds)
        {
            if (t==0)
            {
                FirstCoinRightMove = matrix[currentPosY][currentPosX];
                sj1.add(Integer.toString(FirstCoinRightMove));
            }
                    
            for (int i=1; i<=RIGHTvalue; i++)
            {
                totalCoins = totalCoins + matrix[currentPosY][currentPosX+i];
                
                sj1.add(Integer.toString(matrix[currentPosY][currentPosX+i]));
            }
        }
        
        totalCoins = totalCoins + CoinsOnLastPositionMove;
                    
        FirstCoinRightMove=0;
        CoinsOnLastPositionMove=0;
                    
        coinsCollectedinAllMoves=sj1.toString();
        
        if (currentPosX + RIGHTvalue <matrix[0].length && successfulFinish)
        {
            System.out.println("Successfully moved " + RIGHTvalue + " to the right");
            
            currentPosX = currentPosX +  RIGHTvalue;
                        
            if ((t==numbers.length-1))
            {
                decision(movementPattern, coinsCollectedinAllMoves);
            }
        }
    }
    
    public void movesAlternateDownRight()
    {
        numbers = valuesSet.split(",");
        
        System.out.println("\n\n"+ "{"+valuesSet + "}"+  "   will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********");
        System.out.println(alternatingDownRight);
                
        successfulFinish=true;
        outBounds=false;
            
        for (int t=0; t<numbers.length; t++)
        {
            if (successfulFinish && !outBounds)
            {
                System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
                
                if (t%2==0)
                {
                    movesDown(t, alternatingDownRight);
                    
                }
                
                else
                {
                    movesRight(t, alternatingDownRight );
                }
                
            }
        }   
    }
    
    public void movesAlternateRightDown()
    {
        numbers = valuesSet.split(",");
        
        System.out.println("\n\n"+ "{"+valuesSet + "}"+  "   will be evaluated against the " + matrix[0].length + "x" + matrix.length + " matrix********");
        System.out.println(alternatingRightDown);    
            
        successfulFinish=true;
        outBounds=false;
            
        for (int t=0; t<numbers.length; t++)
        {
            if (successfulFinish && !outBounds)
            {
                System.out.println("You are currently at " + "["+currentPosY+"]"+"["+currentPosX+"]" + " on the matrix");
                
                if (t%2==0)
                {
                    movesRight(t, alternatingRightDown);
                }
                
                else
                {
                    movesDown(t, alternatingRightDown);
                }  
            }
        }   
    }  
}  

class Staircase
{
    String coinsCollectedinMoveString;
    String subsetCycleInformation;
    String direction;
    
    static String[] finalOutput = new String [1000];
    
    int solution;
    
    static int subsetEntry=0;
      
    static int k;
    int[] S;
    
    static int[][] matrix;
    
    int p;
    int total; 
    int cycles=0;
    int maxRValue;
    static int totalcycles=0;
    
    static int difference = 0;
   
    static int i=0;
    
    static List <String> backupValuesSet = new ArrayList<>();
    
    Set<String> st;
    Random rand = new Random();
    
    static String[] valuesSet;
    String []backupValuesSetBeforeModification;
    
    static int newSetSize;
    
    public Staircase(long combinations, int[] X, int r, Set<String> st, int maxRValue, int[][] matrix, int maximumLengthMoves)
    {
        this.k=maximumLengthMoves;
        this.matrix=matrix;
        this.S=S;
        this.st=st;
        this.maxRValue=maxRValue;
        System.out.println("Combinations: " + combinations);
        StringJoiner sj = new StringJoiner(",");
        StringJoiner sj1 = new StringJoiner(",");
        
        int currentSetSize=0;
        
        int q; 
        int steps; 
        boolean allSameDigit=true;
        
        String subsetIntToString="";
        
        int countSameNumber=0;
        int pos=0;
        
        int previousI=0;
        
        int n=0;  
        
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
            
        do
        {
            for (q=0; q<r;q++)
            {
                p= rand.nextInt(X.length);
                steps = X[p];
                sj.add(Integer.toString(X[p]));
                
                currentSetSize=st.size();
                total=total+steps;
                
                if (total==k)
                {
                    st.add(sj.toString());
                }
                
                if (q==r-1)
                {
                    sj = new StringJoiner(",");
                    total=0;
                }
            }
            
            if (total>k)
            {
                
                total=0;
                sj = new StringJoiner(",");
            }
            
            newSetSize = st.size();
         
            cycles++;
          
            totalcycles++;
         
        }while (cycles<combinations*1000);
        //}while (cycles<70);
        
        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
       
        for (String m: backupValuesSet)
        {
            n=0;
            
            do
            {
                if (m==valuesSet[n])
                {
                    valuesSet[n]="ALREADY PROCESSED";
                    
                }
                n++;
                
            }while (n<valuesSet.length);
        }
        
        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size());
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification)); 
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                if (startToFinishRightDown(valuesSet[entry]))
                {
                    System.out.println (valuesSet[entry] +  "    Subset: " + subsetEntry + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + Direction.totalCoins   +"  " + "("+Direction.alternatingRightDown+")" );
              
                    Direction.totalCoins=0;  
                
                    subsetEntry++;
                }
            
                if (startToFinishDownRight(valuesSet[entry]))
                {
                    System.out.println (valuesSet[entry] +  "    Subset: " + subsetEntry + "     " +  "Coins collected{"+Direction.coinsCollectedinAllMoves+"}" + "   " +  "   TOTAL COINS: " + Direction.totalCoins +"  " + "("+Direction.alternatingDownRight+")");
                    Direction.totalCoins=0;
                
                    subsetEntry++;
                }
            }
        }
        
        System.out.println("There are: " + (subsetEntry) + " possibilities SO FAR");
        
        System.out.println("Tested via alternating DOWN and RIGHT along path and also RIGHT and DOWN");
        
        difference = newSetSize;
    }
        
        
    public static boolean startToFinishRightDown(String valuesSet)
    {
        Direction d = new Direction(valuesSet, "RightDown", matrix, newSetSize);
            
        return d.successfulFinish;
    }
        
        
    public static boolean startToFinishDownRight(String valuesSet)
    {
        Direction d = new Direction(valuesSet, matrix, "DownRight", newSetSize);
            
        return d.successfulFinish;
    }
        
}
        
        
public class Combination
{
    static Staircase sc;
    
    public static void main(String[] args)
    {
        System.out.println("Welcome to Online IDE!! Happy Coding :)");
        int originalNumber=0;
    
        int n=originalNumber;
    
        int r;
    
        Set <String> s = new HashSet<>();
    
        int[][] matrix = new int[][]{
                                //{0,0,0,0,0,0,1,0,0,7},
                                //{1,0,0,0,0,0,0,6,0,0},
                                //{0,0,9,0,1,1,1,1,0,1},
                                //{0,0,1,0,0,1,1,9,0,0},
                                //{0,0,1,0,0,0,1,1,1,0},
                                
                                //{0,0,1,6,4},
                                //{0,4,1,3,2},
                                //{0,0,0,9,6},
                                //{0,1,1,1,1},
                              
                                //{0,0,1},
                                //{4,1,1},
                                //{6,9,0},
                                 
                                 {1, 2, 3, 4},
                                 {0, 1, 0, 2},
                                 {3, 0, 1, 0},
                                 {2, 1, 0, 1},
                                
                                };
    
        int [] X = new int [matrix[0].length-1];
    
        for (int k=0; k<matrix[0].length-1; k++)
        {
            X[k]= k+1;
        }
    
        System.out.println("These are possible moves in: " + matrix.length + "x" + matrix[0].length + " matrix:\t" +   Arrays.toString(X));
    
        int maximumLengthMoves = (matrix.length-1) + (matrix[0].length-1);
        System.out.println("Fixed number moves from START to END: " + maximumLengthMoves);
    
        int counter=1;
    
        int minimum;
    
        int maxRValue;
    
        boolean solutionFound=false;
    
        Map <Integer, Long> m;
    
        n=X.length;
    
        originalNumber=n;
    
        m= new HashMap<>();
       
        minimum=X[0];

        for (int i=0; i<X.length;i++)
        {
            if (X[i]<minimum && X[i]!=0)
            {
                minimum=X[i];
            }
        }
        maxRValue=(maximumLengthMoves)/minimum;
    
        if (maxRValue>=64)
        {
            System.out.println("Value of r=" + maxRValue + " is too high computationally. It will be reduced to: " + (maxRValue-1));
        }
    
        System.out.println("Maximum r value: " + maxRValue);
    
        for (r=0; r<=maxRValue; r++)
        {
            System.out.println("\n***COMBINATIONS*** (WITH REPLACEMENT)");
            System.out.println("C^R(n + r) = " + "(n+r-1)! / r!(n-1)!");
        
            System.out.println("C^R(" + n+","+r+") = " + (n+r-1)+ "!" + " / " + r+"!"+"("+(n-1)+")!");
        
            sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue, matrix, maximumLengthMoves);
        }
    
        System.out.println("\n***********SOLUTIONS************");
        
        for (String str: Direction.completedPaths) 
        {
            if(str!=null)
            {
                System.out.println(str);
                solutionFound=true;
            }
        }
        
        if (!solutionFound)
        {
            System.out.println("NO solutions");
        }
        
        Direction.finalResults();
        
        System.out.println("\n\n");
    }

    public static long Combinations (int n, int r, int originalNumber, Map factorialResults)
    {
        long result=0;
        int denominator1;
        int denominator2; 
        int Numerator=n+r-1;
        int zero=0;
        long zeroFactorial = 1;
        
        if (originalNumber==0 && r==0)
        {
            System.out.println("n and r can not both be equal to zero");

            return 0;
        }

    if (originalNumber==0 && originalNumber+r-1<r)
    {
        System.out.println("n+r-1 must be > or = to r");
        
        return 0;
    }
    
    if (Numerator>=1)
    {
        result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults)));
        factorialResults.put(Numerator,result);
        
        if (n==originalNumber)
        {
            denominator1 = r;
            denominator2 = originalNumber-1;
            factorialResults.put(zero,zeroFactorial);
            
            if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2))
            {
                long returnValue = result / ((long)factorialResults.get(denominator1) *(long)factorialResults.get(denominator2));
                return returnValue;
            }
        }
        return result;
    }  
    return 1;
    } 
}