### Problem Statement

A diamond mine is a matrix of ones and zeroes with R rows and C columns.

A diamond is a pattern of ones forming the boundary of a 45-degree rotated square. The diamonds of size 1, 2, and 3 are shown below.

```size 1:   size 2:      size 3:
1
1           1 1
1        1 1         1   1
1           1 1
1
```

The diamond mine in this problem will be pseudo-randomly generated using the following method:

You are given two ints: seed and threshold. Let x0=seed and for all i>=0 let xi+1 = (xi * 25173 + 13849) modulo 65536.

Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, look at the next xi (starting with x1 for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a 1, otherwise it will contain a 0.

Your method shall compute and return the size of the largest diamond that can be found in the mine. If there are no diamonds, return 0.

### Definition

 Class: DiamondMining Method: largestDiamond Parameters: int, int, int, int Returns: int Method signature: int largestDiamond(int R, int C, int seed, int threshold) (be sure your method is public)

### Notes

-The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.

### Constraints

-R will be between 1 and 750, inclusive.
-C will be between 1 and 750, inclusive.
-seed will be between 0 and 65,535, inclusive.
-threshold will be between 0 and 65,536, inclusive.

### Examples

0)

 `5` `5` `47` `20598`
`Returns: 3`
 The generated pseudo-random sequence is 17332, 39133, 37242, 14235, 656, 12265, 20598, 6471, 51372, 44853, 44210, 45363, 37384, 49857, 49710, 19295, 39588, 22157, 60650, 29643, 24192, 38553, 51430, 63095, and 39324. The resulting diamond mine looks as follows: ```0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 ```
1)

 `5` `5` `47` `20599`
`Returns: 2`
 The pseudo-random sequence is the same, but the threshold is larger. The only change in the resulting diamond mine is that now the cell in row 2, column 2 contains a 0, and therefore there is no diamond of size 3.
2)

 `4` `4` `11` `65500`
`Returns: 0`
 No diamonds at all.
3)

 `3` `6` `47` `15000`
`Returns: 2`
 ```1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 ``` The only diamond of size 2 is located on the left side of the mine.
4)

 `200` `300` `42` `0`
`Returns: 100`
 Regardless of the seed, if the threshold is 0, each cell contains a 1. Therefore the size of the largest diamond is only limited by the dimensions of the mine.
5)

 `741` `2` `16435` `65535`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10286

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13730&pm=10286

misof

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming