booking woman in tech - Manhattan 2 - score 23.75, timeout, runtime error - started to work on extra a few hours to score 30

Manhattan2_score23.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Manhattan2
{
    /// <summary>
    /// https://www.hackerrank.com/contests/booking-womenintech/challenges/manhattan-2
    /// The idea is to start from top left node, always go right or down, and then track the 
    /// sum and max value; 
    /// Because the size of matrix is 100 * 100, queue will cause out-of-memory, use stack, DFS 
    /// search, try to use recursive solution if possible
    /// 200 depth at most, 100 + 100
    /// try to get some points first, and then get the idea - 2:35pm 
    /// 
    /// </summary>
    class Manhattan2
    {
        internal class Node
        {
            public int sum { get; set; }
            public int maxValue { get; set; }
            public string trackNode { get; set; }
            public int candies
            {
                get
                {
                    return sum + SecondsLeft * maxValue;
                }
            }
            
            public int SecondsLeft { get; set; }
        }

        static void Main(string[] args)
        {
            ProcessInput(); 
            //RunTestcase(); 
        }

        public static void RunTestcase()
        {            
            int rows = 5;
            int cols = 5;
            int seconds = 12;

            var matrix = new int[rows][];
            matrix[0] = new int[] {2, 1, 1, 1, 1 };
            matrix[1] = new int[] {2, 2, 1, 1, 1 };
            matrix[2] = new int[] {1, 2, 1, 1, 1 };
            matrix[3] = new int[] {2, 2, 1, 1, 3 }; 
            matrix[4] = new int[] {2, 2, 2, 2, 2 }; 

            var node = new Node();
            int maximumCandies = int.MinValue;

            FindRouteFromLeftTopToBottomRight(matrix, seconds, ref node, ref maximumCandies, 0, 0);

            Console.WriteLine(maximumCandies);    
        }

        public static void ProcessInput()
        {
            var numbers = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            int rows = numbers[0];
            int cols = numbers[1];
            int seconds = numbers[2];

            var matrix = new int[rows][];
            for (int i = 0; i < rows; i++)
            {
                matrix[i] = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            }

            if (seconds < rows - 1 + cols - 1)
            {
                Console.WriteLine("Too late");
                return;
            }

            var node = new Node();
            int maximumCandies = int.MinValue;

            FindRouteFromLeftTopToBottomRight(matrix, seconds, ref node, ref maximumCandies, 0, 0);

            Console.WriteLine(maximumCandies);         
        }


        /// <summary>
        /// Always go two directions
        /// down or right 
        /// </summary>
        /// <param name="matrix"></param>
        /// <param name="seconds"></param>
        /// <returns></returns>
        public static void FindRouteFromLeftTopToBottomRight(
            int[][] matrix, 
            int seconds, 
            ref Node node, 
            ref int maximumCandies, 
            int startRow, 
            int startCol)
        {
            int rows = matrix.Length;
            int cols = matrix[0].Length; 
             
            if(seconds == 0 || isLastNode(startRow, startCol, rows, cols))
            {
                var current = matrix[startRow][startCol];
                node.sum += current;
                node.SecondsLeft = seconds; 
                int currentCandies = node.candies;

                maximumCandies = (currentCandies > maximumCandies) ? currentCandies : maximumCandies;
                return; 
            }

            // go to right
            if (startCol < cols - 1 )
            {
                var current = matrix[startRow][startCol];
                var currentMax = node.maxValue; 
                //var currentTrack = node.trackNode; 
                //var currentKey = encode(startRow, startCol); 

                var rightNode = new Node();
                rightNode.sum = node.sum + current;
                rightNode.maxValue = (current > currentMax) ? current : currentMax;
               // rightNode.trackNode = (currentTrack == null) ? currentKey : (currentTrack + currentKey);

                FindRouteFromLeftTopToBottomRight(matrix, seconds - 1, ref rightNode, ref maximumCandies, startRow, startCol + 1);
            }

            // go down
            if (startRow < rows - 1 )
            {
                var current = matrix[startRow][startCol];
                var currentMax = node.maxValue;
                //var currentTrack = node.trackNode;
                //var currentKey = encode(startRow, startCol); 

                var downNode = new Node();
                downNode.sum = node.sum + current;
                downNode.maxValue = (current > currentMax) ? current : currentMax;
                //downNode.trackNode = (currentTrack == null) ? currentKey : (currentTrack + currentKey);

                FindRouteFromLeftTopToBottomRight(matrix, seconds - 1, ref downNode, ref maximumCandies, startRow + 1, startCol);
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="startRow"></param>
        /// <param name="startCol"></param>
        /// <returns></returns>
        private static string encode(int startRow, int startCol)
        {
            return "[" + startRow + "-" + startCol + "]"; 
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="startRow"></param>
        /// <param name="startCol"></param>
        /// <param name="rows"></param>
        /// <param name="cols"></param>
        /// <returns></returns>
        private static bool isLastNode(int startRow, int startCol, int rows, int cols)
        {
            return startRow == (rows - 1) && startCol == (cols - 1); 
        }
    }
}