题目描述

译自 ROIR 2017 Day1 T4. Полезные ископаемые

在一个邻近星系的行星开发项目中，计划派遣多批机器人到该行星上开采矿产资源。

计划开采矿产的行星表面区域是一个大小为 $w \times h$ 的网格矩形，网格单元的坐标范围从 $(1,1)$ 到 $(w, h)$。该区域内的一些单元设有专家基地，可以接收机器人批次。总共有 $s$ 个基地，第 $i$ 个基地位于坐标为 $(x_i, y_i)$ 的单元。

每批机器人由三个参数定义：第 $j$ 批机器人被送往基地 $b_j$，包含 $n_j$ 个机器人，每个机器人的移动能力为 $m_j$。

当一批机器人被送到相应基地时，该批中的每个机器人从基地移动到行星表面上的某个单元。如果一个机器人的移动能力为 $m$，它最多可以向八个方向中的一个移动 $m$ 次，如下图所示。

在所有批次的机器人到达并安置在区域内后，它们将被激活并开始开采矿产资源。在移动过程中，一个单元内可以同时容纳任意数量的机器人。然而，激活后，每个单元内最多只能有 $q$ 个机器人。

项目领导层收到了关于 $t$ 批可依次发送到行星的机器人信息。在考虑到移动能力限制的情况下，送达所有批次的机器人后，可能无法将机器人安置在区域内，使得每个单元内不超过 $q$ 个机器人。因此，领导层必须选择前 $k$ $(0 \leq k \leq t)$ 批机器人完全送达相应基地。如果 $k < t$，则需额外从第 $(k+1)$ 批机器人中接收 $z$ $(0 \leq z \leq n_{k+1})$ 个机器人。

所有接收到的机器人必须在移动能力限制下安置在区域内，每个单元内不得超过 $q$ 个机器人。之后，它们将被激活并开始开采矿产资源。当然，项目领导层希望最大化送达行星的机器人数量，因此在上述限制下，需要最大化 $k$，然后最大化 $z$。

你的任务是编写一个程序，根据区域大小、数值 $q$、基地位置描述、计划机器人批次数量及其描述，确定最大值 $k$（机器人批次数量），以及随后从第 $(k+1)$ 批中额外接收的最大机器人数量 $z$，以便将机器人送达行星后，能够将它们安置在区域内，使得每个单元内不超过 $q$ 个机器人。

输入格式

输入文件的第一行包含数字 $w, h, s, q$ $(1 \leq w, h \leq 10^{5}, 1 \leq s \leq 4, 1 \leq q \leq 100)$。接下来的 $s$ 行，每行包含两个整数 $x_i, y_i$ $(1 \leq x_i \leq w, 1 \leq y_i \leq h)$，描述专家基地的位置。

下一行包含数字 $t$ $(1 \leq t \leq 100)$，表示机器人批次数量。接下来的 $t$ 行描述机器人批次，每行包含三个整数 $b_j, n_j, m_j$ $(1 \leq b_j \leq s, 1 \leq n_j \leq w \cdot h \cdot q, 0 \leq m_j < \max(w, h))$。

输出格式

输出两个数字 $k$ 和 $z$，其中 $0 \leq k \leq t$。如果 $k = t$，则 $z$ 必须为 $0$；否则，应满足 $0 \leq z < n_{k+1}$。

4 3 2 1
1 1
3 2
3
1 4 1
2 9 1
1 12 2

1 7

在给出的样例中，应完全接收第一批机器人，并额外从第二批中接收 $7$ 个机器人。下图展示了如何将这些机器人安置在区域内，使得每个单元内不超过一个机器人。专家基地用圆圈表示。从基地 $1$ 出发的机器人所在的单元用垂直条纹表示，从基地 $2$ 出发的机器人所在的单元用灰色表示。

数据范围与提示

详细子任务附加限制及分值如下表所示：