Algorithm - Costliest Possible Route in Grid Puzzle Objective

Find the most expensive path from the top-left of a square grid to the bottom-right such that its total cost is below a given threshold.

Scenario


You are given a square NxN grid.
You are given a maximum cost.
Every cell in the grid has a cost. The top-left cell has cost 0.
The cost of a path is the sum of the costs of the cells in the path. Its "cost surplus" is the result of subtracting its cost from the maximum cost.
Movement is always either right one cell or down one cell.
The starting point is the top-left cell of the grid and the goal is the bottom-right cell.
You must output the smallest cost surplus of any path with a non-negative cost surplus, or -1 if there is no such path (The maximum cost is not enough).


Input restrictions


N will be between 1 and 20 inclusive.
The maximum cost will be between 1 and 200 inclusive.
The cost of each cell will be between 0 and 10 inclusive.


Examples


Maximum cost: 9
Grid:

0 1 5
2 3 2
2 3 2


Expected output: 0
Explanation: there is a path 0 2 2 3 2 with cost 9 and cost surplus 0.
Maximum cost: 15
Grid:

0 1 5
2 3 2
2 3 2


Expected output: 5
Explanation: the most expensive path is 0 1 5 2 2 with cost 10 and cost surplus 5.
Maximum cost: 6
Grid:

0 1 5
2 3 2
2 3 2


Expected output: -1
Explanation: the least expensive path is 0 1 3 2 2 with cost 8, which is greater than 6.
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;;