Barbosa's Pacific Escape

Barbosa starts at cell (1,1) in an n×m matrix, and his destination, the Pacific, is located at cell (n,m). Each cell (i,j) has an associated danger value \(d_{ij}\).

He has captured \(k\) Indians. The i-th Indian knows a safe rectangular region specified by its top‐left coordinate \((ax_i, ay_i)\) and bottom‐right coordinate \((bx_i, by_i)\). If Barbosa takes that Indian along, then all cells within that rectangle will be safe (i.e. their danger value is considered 0).

Barbosa must move from (1,1) to (n,m) by moving only right or down (i.e. 4-connected directions) so that his path contains exactly \(n+m-1\) cells. He is allowed to bring at most \(w\) Indians. Determine the minimum possible total danger value along some valid path when Barbosa is allowed to nullify the danger in the covered regions by taking at most \(w\) Indians.

inputFormat

The first line contains four integers: n m k w.

Then follow n lines, each containing m integers. The j-th integer in the i-th line is the danger value \(d_{ij}\) of cell (i,j).

Then follow k lines, each containing four integers: ax_i ay_i bx_i by_i, denoting the top‐left and bottom‐right coordinates of the safe region provided by the i-th Indian. All indices are 1-indexed.

outputFormat

Output a single integer: the minimum total danger value along any valid path from (1,1) to (n,m) after optionally nullifying the dangers in at most w chosen safe zones.

sample

2 2 1 1
1 2
3 4
1 2 2 2

1