Giải bài trực tuyến

The landlord has a rectangular land divided into a grid of M rows and N columns. The rows are numbered from the top to the bottom starting from 1, and the columns are numbered from the left to the right starting from 1. The intersection between the i^th row and the j^th column (i=1..M,j=1..N) has a height of h_ij. The landlord has offered to exchange his land for Bom's magic fan. Here's the condition of the offer:

• Bom can pick two sub-pieces of land (one for housing and one for gardening). Both pieces should have rectangular shape and contain a whole number of cells.
• Each piece should have its height difference not exceeding K, i.e. the difference between its highest cell and its lowest cell does not exceed k.
• The two pieces should not overlap each other (though they can be in contact).
• Please help Bom to pick the two pieces of land satisfying the above conditions and have the largest sum of areas.

Input

• The first line contains three integers M, N and K (M,N≤300).
• Each line in the next M lines contains N integers h_ij describing the land.(K,|h_ij|<10⁹)

Output

A single number that is the largest possible sum of areas of Bom's two pieces of land.

Example

Input
3 4 0
1 2 3 1
1 9 9 1
2 2 2 2	

Output
6

Note: There are 50% test cases in which m,n≤50.