Rotate Array 4

For an array A of size N×M, the value of array A is the minimum among the sums of all numbers in each row. If array A is as follows, the sum of row 1 is 6, the sum of row 2 is 4, and the sum of row 3 is 15. Therefore, the value of array A is 4.

1 2 3
2 1 1
4 5 6

The array can undergo rotation operations. A rotation operation consists of three integers (r, c, s) and means rotating the square whose top-left cell is (r-s, c-s) and whose bottom-right cell is (r+s, c+s) clockwise by one cell. Cell (r, c) of the array means row r, column c.

For example, if array A has size 6×6 and the rotation operation is (3, 4, 2), it rotates as shown in the figure below.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

When there are two or more rotation operations, the final array differs depending on the order in which the operations are performed.

The following is an example where array A has size 5×6 and the rotation operations are (3, 4, 2), (4, 2, 1).

| Array A                                                             | After operation (3, 4, 2)                                               | After operation (4, 2, 1)                                               |
| ```
1 2 3 2 5 6
3 8 7 2 1 3
8 2 3 1 4 5
3 4 5 1 1 1
9 3 2 1 4 3
``` | ```
1 2 3 2 5 6
3 8 7 2 1 3
3 8 2 1 4 5
9 4 3 1 1 1
3 2 5 1 4 3
``` | ```
1 8 2 3 2 5
3 8 2 7 2 6
3 4 3 1 1 3
9 2 1 1 4 5
3 5 1 4 3 1
``` |
| Array A                                                             | After operation (4, 2, 1)                                               | After operation (3, 4, 2)                                               |

If operations are performed on array A in the order (3, 4, 2), (4, 2, 1), the value of array A is 12, and if performed in the order (4, 2, 1), (3, 4, 2), it is 15.

Given array A and the available rotation operations, find the minimum value of array A. Every rotation operation must be used exactly once, and the order may be chosen freely.

The first line gives the size N, M of array A and the number of rotation operations K.

From the second line, N lines give the numbers A[i][j] contained in array A, and the following K lines give the information r, c, s of the rotation operations.

Print the minimum value of array A.

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M