小明在学习魔法，今天学习的魔法叫石子阵，这个魔法可以让 $30$ 颗石子堆成一个石子堆，并且指挥很多个石子堆共同移动。

小明把练习魔法的地方划成了很多个 $1 \times 1$ 的方格，他指挥的 $n$ 个石子堆都在某一个方格里，第 $i$ 个石子堆的坐标是 $(x_i,y_i)$。每秒钟都要做一次整体移动，每次移动的时候，所有石子堆都同时向一个方向（东/E、南/S、西/W、北/N）移动一个格子。这里的方格和方向，符合平面直角坐标系和上北下南左西右东的原则。也就是说，$x$ 轴从左往右，$y$ 轴从下往上，北/N 是从下往上的方向，和 $y$ 轴的方向一致。

在这些方格中，有 $m$ 个方格是神秘方格，第 $i$ 个神秘方格的坐标是 $(X_i,Y_i)$。神秘方格有隐藏洞穴，当石子堆移动到神秘方格的时候，最下方的那个石子将会掉进洞穴，消失不见。如果此时石子堆只有一颗石子，那么这颗石子会消失不见，整个石子堆也会消失不见。

突然，负责侦查的机器人告诉小明，魔法老师马上要来了，要赶紧把所有的石子藏起来。小明有 $k$ 秒钟的时间，他想知道通过移动石子堆，最多可以让多少颗石子消失。小明知道，在一开始的时候，没有任何一个石子堆在神秘方格的位置。

———————————————— 题解

注意到 $k \le 30$，相当于石子堆上的石子数量是无限多的。

题意可简述为：平面直角坐标系中有 $n$ 个点和 $m$ 个标记，每秒钟所有点平移一个单位，每次遇到标记答案加一，问 $k$ 秒后答案最大是多少，并且求字典序最小的移动序列。

考虑 DP。

$dp[i][j][t]$ 表示第 $t$ 秒，水平偏移量为 $i$，垂直偏移量为 $j$ 时的答案最大值。（注意：$i,j$ 可能是负数）

显然有 $dp[i][j][t]=\max\{dp[i-dx[p]][j-dy[p]][t-1]\}+cnt[i][j]$，其中 $cnt[i][j]$ 表示移动到偏移量为 $i,j$ 时对答案的贡献，可以预处理。

最后的答案就是 $\max\{dp[i][j][k]\}$。

边界条件是 $dp[0][0][0]=1$，其他的 $dp[i][j][0]=-\infty$（不存在的状态）

求出答案后，从目标状态出发，反过来求移动序列。注意可能不止一个目标状态，所以计算移动序列时要按层，并且最终从起始状态开始输出结果。

——————————————————————— 违规紫衫，主要是模拟赛没做出来，有必须订正的要求，但是就算有题解我也实在在不会做