### Problem Statement

A Company that Makes Everything (ACME) has entered the surface mining business. They bought a rectangular field which is split into cells, with each cell having a profit value. A mine is a non-empty rectangular region, and the profit of a mine is equal to the sum of the values of all its cells. ACME wants to extract ore from three different non-overlapping mines. You are to choose these mines to maximize the total profit.

You are given a String[] field where each character represents the profit value of a single cell. Characters 'a' to 'z' correspond to the numbers 0 through 25 and characters 'B' to 'Z' correspond to numbers -1 through -25. The jth char in the ith element of field is the profit value of the cell at row i, column j.

### Definition

 Class: ThreeMines Method: maximumProfit Parameters: String[] Returns: int Method signature: int maximumProfit(String[] field) (be sure your method is public)

### Constraints

-field will contain between 1 and 30 elements, inclusive.
-Each element of field will contain between 1 and 30 characters, inclusive.
-Each character of field will be from the set 'a'..'z' and 'B'..'Z'.
-All elements of field will contain the same number of characters.
-field must contain at least 3 cells.

### Examples

0)

 ```{ "bbbb", "bBBB", "BBbb", "BBBB"}```
`Returns: 7`
 One of the optimal solutions is the following: One mine contains all cells in the first row, the second mine contains the cell (1, 0), and the third mine contains the cells (2, 2) and (2, 3).
1)

 `{"cfCBDCbcdZb"}`
`Returns: 14`
 A single row example.
2)

 ```{"d", "c", "B", "m", "Z", "h", "g", "B", "z", "G", "H", "b", "Y"} ```
`Returns: 54`
 A single column example.
3)

 ```{ "hBhh", "BBBB", "BBBB", "hBhh", "hBhh"}```
`Returns: 62`
 This test has only one solution.
4)

 ```{ "BB", "BB"}```
`Returns: -3`
 It is possible for the maximum possible profit to be negative.
5)

 ```{ "ZcabcaacacabcbbbcababacaccbZaa", "acaaccccacbccbaaccabaccaacbZbc", "bcbaacbcbbccbbcbabbbbaZcbcbccb", "cccacbabccbZbcbabaacbbZcbacbab", "cacbabbcabbabbcacbcbbcaacaabbc", "bacZcacaaccbabbcccccabcaacbaca", "cbcccacabcabacaccacaZbbcbcacbb", "cZbbbcaacbaacaabZcaccbcZccbbab", "Zcababaacbbbbccbcbbaccacacbbcc", "cZcccaaabbcbcbccccbcbaabbbccbb", "bbcaacacabccababacbccacccbbaba", "cccbbcaZabccacabbccccabbabbbab", "bbbacbccbbcaabaaabccbcaabcacaa", "cbbababbccccbcccbaacacccaabaac", "aaccaccaccbabbccaaaacbacccacca", "bbbcabcabZZcabcabbaacZbaaabaZb", "aaabbabcabaaacbcccccbbcabcccbc", "bbbaccbacacaccbbaccabacbbbaaac", "acaaacccbabbccbcbabbcbaaaccabb", "bcaaaaabcbabaaabccacccbaacbbbc", "bZcbcbcccaabccaabbccbababbbcca", "cbbbbcccabcabcbacaaaaabbbbbcac", "ccbbcbacacbbcacacbaabcbbacbaba", "cbbbaabaabbbbaccabbcbcaccaaaac", "abZcabaacbbcacbaaabccbabacacaa", "aabccacbabaacaccccbbbbcccccaca", "aabcbaaacbabcaccbaabbbabbabbca", "ababcabaccaaaacccacbcbcabacbcb", "bcaaaacabcabbbaccccccacabccacb", "cbbabbbccaaaaacbccaabcbbccbacc"}```
`Returns: 671`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9995&pm=6625

Cosmin.ro

#### Testers:

PabloGilberto , brett1479 , vorthys , Olexiy

#### Problem categories:

Dynamic Programming