MATRIX2 - Submatrix of submatrix

You are given a matrix P of N rows and M columns. It consists of integer numbers in the range [1..100]. We define the sum of a matrix is the sum of its elements. Your task is to find a submatrix Q (of A rows and B columns) of P and a submatrix K (of C rows and D columns) of Q so that the difference between the sum of Q and the sum of K is maximal, and submatrix K is absolutely inside matrix Q (i.e no element on matrix Q's sides is also in matrix K).

Because the tests are large, we suggest a method to define matrix P:
P[i][j] = ( P[i][j-1] * 71 + 17 ) mod 100 + 1 . ( 1 ≤ i ≤ N , 1 ≤ j ≤ M )
With this method we only care about P[i][1].

Constraints
1 ≤ N , M ≤ 1000
1 ≤ A ≤ N
1 ≤ B ≤ M
0 ≤ C ≤ A - 2
0 ≤ D ≤ B - 2

Input

The first line of the input contains an integer t (1 ≤ t ≤ 10 ), equal to the number of testcases. Then descriptions of t testcases follow. The first line of the description contains 6 integer numbers N, M, A, B, C, D. Then N lines follow, line i contains one integer number P[i][1].

Output

For each test case, your program should output the maximal difference between two matrices (in a separate line).

Example

Input:
1
3 3 3 3 1 1
1
2
3

Output:
260

Added by:Nguyen Dinh Tu
Date:2006-08-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Base on a problem in IOI 2006 .

hide comments
2017-11-10 15:55:55 Janusz Kowalski
Perhaps the following set of constraints would be more clear:

2 ≤ N , M ≤ 1000
2 ≤ A ≤ N
2 ≤ B ≤ M
0 ≤ C ≤ A - 2
0 ≤ D ≤ B - 2

?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.