BYU15W_3 - Largest Product

no tags 

Your task is to take an N-by-N grid and determine the greatest product of any X adjacent numbers in the same direction (up, down, left, right, or diagonally – think Connect 4).

Example

In this example, N = 4 and X = 4.

 99 134
1 90 24
23 80 2
342 85 

The largest 4-term product in this 4 × 4 grid is 99 * 90 * 80 * 85 = 60588000.

Input

The first line contains two positive integers N and X. N is the size of the grid and X is the number of terms to be multiplied together. The next N lines each contain N whitespace-separated non-negative integers each less than 100.

Constraints

1 <= X <= N <= 10

Output

Output a single line containing the largest X-term product in the grid.

Example

Input:
4 4
99 1 3 4
1 90 2 4
2 3 80 2
3 4 2 85

Output:
60588000
Input:
5 3
1 2 3 4 5
6 5 4 3 2
3 4 5 6 7
8 7 6 5 4
5 6 7 8 9

Output:
504

hide comments
matematikaadit: 2015-04-14 07:10:08

If you don't know what is Connect 4, it's a game here http://en.wikipedia.org/wiki/Connect_Four


Added by:BYU Admin
Date:2015-03-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64