Algorithm - Costliest Possible Route in Grid Puzzle
CJam, 72 71 bytes
q~:Q,mqi:L(2*0aa\{{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*{Qf=:+}%f-{W&gt;},$W+0=

This is really long and I think a different approach to the question is the only way to get it shorter.
Try it online here
Input is in the following format : &lt;Steps&gt; [&lt;Flat Grid&gt;] . For ex:
9 [0 1 5 2 3 2 2 3 2]

And output is the cost remaining, so 1 in above example.
*Note that [0 1 5 2 3 2 2 3 2] is just a flat representation of the grid
0 1 5
2 3 2
2 3 2

How it works (slightly outdated):
q~                                     &quot;Read the input and evaluate it&quot;;
  :Q                                   &quot;Store the array in Q&quot;;
    ,mqi:L                             &quot;Do floor of square root of its length&quot;;
          LL+((                        &quot;Double length and decrease 2 from the double&quot;;
               0aa                     &quot;Put [[0]] on stack. This is the starting index&quot;
                                       &quot;for any path in the grid&quot;;
                  \{ ... }*            &quot;Swap to but L + L - 1 on top and run the code&quot;
                                       &quot;block that many times&quot;;
 {{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*    &quot;This block calculates indexes of all possible&quot;;
                                       &quot;paths from top left to bottom right of the grid&quot;;
 {                            }%       &quot;Map each array based on this code block&quot;;
  _[~                                  &quot;Copy the array and start a new array with the&quot;
                                       &quot;contents of the copied one&quot;;
     __                                &quot;Make two copies of the last element of the array&quot;;
       )L%                             &quot;Increment the element and calculate module L&quot;;
          1L?                          &quot;Choose L if module is 0, 1 otherwise&quot;;
             +]                        &quot;Add it to the copy of last array element. With&quot;
                                       &quot;this, we have created one of the two possible&quot;
                                       &quot;next step, that is going right. Except if we are&quot;
                                       &quot;on the last column, then go down&quot;;
               \[~                     &quot;Swap and start a new array with contents of&quot;
                                       &quot;the original array&quot;;
                  __                   &quot;Make two copies of the last element&quot;;
                    L/)                &quot;Divide the 2nd copy by L and add 1 to the result&quot;;
                       L=1L?           &quot;If index belongs to last row, choose 1, else L&quot;;
                            +]         &quot;Add to the first copy of last element and close&quot;
                                       &quot;the array. Now we have the second possible next&quot;
                                       &quot;step, i.e. going down. But if we are on last row&quot;
                                       &quot;then go right&quot;;
{Qf=:+}%                               &quot;Map this block on the array containing all&quot;
                                       &quot;possible path indexes&quot;;
 Qf=                                   &quot;Get the corresponding cell amount array&quot;;
    :+                                 &quot;Sum the array elements to get total path cost&quot;;
        {1$)&lt;},                        &quot;Filter out paths which are not possible. i.e.&quot;
                                       &quot;paths having total cost more than first input&quot;;
               $W=                     &quot;Sort and get the last (highest) path cost&quot;;
                  -                    &quot;decrement from input to get remaining steps&quot;;