# 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 , 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

• Some brute force algorithms for this could be very slow. Are there any restrictions on time for cases like the first test case? Jan 28 '16 at 1:36
• @steveverrill. For this challenge, no time complexity will count, but if you answer this and prove that your method is efficiently better than brute force I will gladly upvote your answer. Jan 28 '16 at 8:12

# JavaScript (ES6), 190 bytes

(m,n)=>m.map((a,r)=>a.map((_,c)=>f(r,c,[0],0)),o=f=(x,y,s,t)=>s[n]?o>t?0:o=t:s.indexOf(w=x+","+y)<0&&m[y]&&(v=m[y][x])<1/0&&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)=>
m.map((a,r)=>                 // for each row
a.map((_,c)=>               // 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)=>               // recursive function f, x & 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>t?0:o=t               // set o to max of o and t
:s.indexOf(w=x+","+y)<0&& // if the square has not been used yet
m[y]&&(v=m[y][x])<1/0&&   // and the square is not out of bounds
// ( if value of square is less than Infinity )

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)=>m.map((a,r)=>a.map((_,c)=>f(r,c,[0],0)),o=f=(x,y,s,t)=>s[n]?o>t?0:o=t:s.indexOf(w=x+","+y)<0&&m[y]&&(v=m[y][x])<1/0&&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
<textarea rows="7" cols="40" id="Matrix">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</textarea><br />
N = <input type="number" id="N" value="6" /><br />
<button onclick="result.textContent=solution(Matrix.value.split('\n').map(x=>x.split(' ').map(z=>+z)),N.value)">Go</button>
<pre id="result"></pre>