Matrix Sum (APCS 2020-01 Intermediate)

An \(n\times m\) matrix has \(n\) rows and \(m\) columns. The entry in row \(i\), column \(j\) of matrix \(X\) is denoted by \(X_{i,j}\).

For two matrices of the same size, their matrix distance is the number of aligned positions containing different values. For example,

differ at the upper-right and lower-right positions, so their matrix distance is \(2\).

You are given a small \(s\times t\) matrix \(A\) and a large \(n\times m\) matrix \(B\). Selecting \(s\) consecutive rows and \(t\) consecutive columns from \(B\) produces a submatrix with the same size as \(A\).

If a submatrix has its upper-left corner at row \(x\), column \(y\) of \(B\), it contains

The legal upper-left corners satisfy

Inspect every such submatrix:

1. A submatrix is eligible when its matrix distance from \(A\) is at most \(r\).
2. Report the number of eligible submatrices.
3. For every eligible submatrix, compare the sum of all its entries with the sum of all entries in \(A\), and find the minimum absolute difference.

Matrix distance is used only for eligibility; the second output compares entry sums. These are two different quantities. Overlapping submatrices are counted separately.

Input

The first line contains five positive integers \(s,t,n,m,r\).

The next \(s\) lines each contain \(t\) integers describing matrix \(A\).

The following \(n\) lines each contain \(m\) integers describing matrix \(B\).

Constraints

• \(1\le s\le n\le10\)
• \(1\le t\le m\le100\)
• \(1\le r\le100\)
• \(0\le A_{i,j},B_{i,j}\le9\)
• All input values are integers.

Output

On the first line, print the number of submatrices whose matrix distance from \(A\) is at most \(r\).

If at least one eligible submatrix exists, print on the second line the minimum absolute difference between its entry sum and the entry sum of \(A\). If no eligible submatrix exists, print \(-1\) on the second line.

Scoring

The two samples are judged but carry no points. There are exactly \(20\) scored groups, each worth \(5\) points:

• Groups \(1\)–\(10\) (\(50\) points): \(s=n=1\).
• Groups \(11\)–\(20\) (\(50\) points): no additional constraints.

Sample Input 1

1 3 1 10 1
7 4 7
6 7 7 7 4 5 0 4 4 7

Sample Output 1

3
2

Sample Explanation 1

Matrix \(B\) contains \(8\) contiguous submatrices of length \(3\). Three of them have matrix distance at most \(1\) from \(A=[7,4,7]\). Among those three, the minimum absolute entry-sum difference is \(2\).

Sample Input 2

3 3 5 5 2
1 2 1
2 4 2
2 4 5
1 2 1 2 3
2 4 2 4 2
2 4 2 3 5
3 2 4 2 0
3 2 4 5 5

Sample Output 2

3
1

Sample Explanation 2

The three eligible submatrices have upper-left corners \((1,1)\), \((1,3)\), and \((3,2)\). Their matrix distances are \(1,2,2\), respectively.

The entry sum of \(A\) is \(23\), while the three submatrix sums are \(20,24,28\). Therefore, the minimum absolute difference is

Source

APCS January 2020 implementation problem 2; rules based on ZeroJudge h027 “Matrix Sum” and Wang Yizhe's explanation. The statements were newly prepared for AACPOJ.