CF15D Map

给你一个 $n\times m$ 的矩形，你需要从中依次选出若干个 $a\times b$ 矩形直至无法再选择，依次选择的矩形满足以下条件： 1. 此矩形不能和之前的矩形重叠。 1. 这个矩形在所有可选矩形中的花费最小。一个矩形的花费为：此矩形的权值和 $-$ 此矩形最小权值 $\times $ 矩形大小。 1. 如果有多个花费最小的矩形，则优先选行坐标最小的，其次选列坐标最小的。

第一行四个正整数 $n,m,a,b$。 接下来 $n$ 行，每行 $m$ 个正整数。

第一行一个整数 $q$ 表示一共有 $q$ 个矩形依次被选择。 接下来 $q$ 行，每行三个整数 $x_i,y_i,w_i$ 。表示选择的第 $i$ 个矩形左上角的行列坐标，以及该矩形的花费。