The powerful connection Introduction

There is a plantation defined by one big square-board like this one:



The numbers inside each small square represents its area's value/cash/...

The farmer needs help to find the N squares that connected (it means all N squares should have at least one shared border) give him the greatest value.

For example:

If N=1, then the output must be 140.

If N=6, then..



..the output must be 315.

Challenge

Your program/function must take the the matrix's values and the number N as input/arguments and must output the powerful connection's value.

Since this is code-golf, the shortest answer in bytes wins!

Examples

Input:

10 -7 11 7 3 31
33 31 2 5 121 15
22 -8 12 10 -19 43
12 -4 54 77 -7 -21
2 8 6 -70 109 1
140 3 -98 6 13 20
6


Output: 315



Input:

35 -7
-8 36
2


Output: 29
JavaScript (ES6), 190 bytes

(m,n)=&gt;m.map((a,r)=&gt;a.map((_,c)=&gt;f(r,c,[0],0)),o=f=(x,y,s,t)=&gt;s[n]?o&gt;t?0:o=t:s.indexOf(w=x+","+y)&lt;0&amp;&amp;m[y]&amp;&amp;(v=m[y][x])&lt;1/0&amp;&amp;f(x+1,y,s=[...s,w],t+=v)+f(x,y+1,s,t)+f(x-1,y,s,t)+f(x,y-1,s,t))|o


Explanation

Takes the matrix as an array of arrays.

Starts from each square then uses a recursive function to test every possible combination. This is a brute-force approach, but it finishes almost instantly for the first test case on my machine.

(m,n)=&gt;
  m.map((a,r)=&gt;                 // for each row
    a.map((_,c)=&gt;               // for each column
      f(r,c,[0],0)              // start checking paths from the coordinate of the square
    ),
    o=                          // o = output number (max total)
    f=(x,y,s,t)=&gt;               // recursive function f, x &amp; y = current square, t = total
                                // s = array of used squares (starts as [0] so length = +1)
      s[n]?                     // if we have used n squares
        o&gt;t?0:o=t               // set o to max of o and t
      :s.indexOf(w=x+","+y)&lt;0&amp;&amp; // if the square has not been used yet
      m[y]&amp;&amp;(v=m[y][x])&lt;1/0&amp;&amp;   // and the square is not out of bounds
                                // ( if value of square is less than Infinity )

        // Check each adjacent square
        f(x+1,y,
          s=[...s,w],           // clone and add this square to s
          t+=v                  // add the value of this square to the total
        )
        +f(x,y+1,s,t)
        +f(x-1,y,s,t)
        +f(x,y-1,s,t)
  )
  |o                            // return output


Test



var solution = (m,n)=&gt;m.map((a,r)=&gt;a.map((_,c)=&gt;f(r,c,[0],0)),o=f=(x,y,s,t)=&gt;s[n]?o&gt;t?0:o=t:s.indexOf(w=x+","+y)&lt;0&amp;&amp;m[y]&amp;&amp;(v=m[y][x])&lt;1/0&amp;&amp;f(x+1,y,s=[...s,w],t+=v)+f(x,y+1,s,t)+f(x-1,y,s,t)+f(x,y-1,s,t))|o
&lt;textarea rows="7" cols="40" id="Matrix"&gt;10 -7 11 7 3 31
33 31 2 5 121 15
22 -8 12 10 -19 43
12 -4 54 77 -7 -21
2 8 6 -70 109 1
140 3 -98 6 13 20&lt;/textarea&gt;&lt;br /&gt;
N = &lt;input type="number" id="N" value="6" /&gt;&lt;br /&gt;
&lt;button onclick="result.textContent=solution(Matrix.value.split('\n').map(x=&gt;x.split(' ').map(z=&gt;+z)),N.value)"&gt;Go&lt;/button&gt;
&lt;pre id="result"&gt;&lt;/pre&gt;