Solution
对坐标离散化，设 $f_{i,j}$ 表示能否到达 $(i,j)$，每次可以用一个点转移到新的位置，时间复杂度 $O(n^3)$。
优化转移，对右上记为第一类转移，对右侧记为第二类转移，对上方记为第三类转移。
若转移到 $x,y$，则三种转移条件分别为
$$2x+2y-\max_{i\in[0,x-1],j\in[0,y-1],f_{i,j}=1}(i+j)\le m$$
$$2x+y-2\max_{i\in[0,x-1],f_{i,y}=1}i\le m(miny_x\le y)$$
$$x+2y-2\max_{j\in[0,y-1],f_{x,j}=1}j\le m(minx_y\le x)$$
对三类转移分开转移，即可做到时间复杂度 $O(n^2)$。
对点按横坐标 $x$ 排序，从左到右扫描线，尝试使用线段树优化转移。
维护一个单调栈以维护每个纵坐标 $y$ 对应的最大合法横坐标 $p_y$。
对于第一类转移，一定是转移到某个输入的点，对于每一个 $y$，从某个 $(p_y,y)$ 转移过来是最优的，所以需要在线段树上维护 $\max(p_y+y)$。
对于第二类转移，发现对于每一个单调栈区间，$y$ 增加时代价单调递增，所以一定为前缀合法，后缀非法的形式。每次得到一个单调栈区间时，在线段树上对非法位置区间删除。虽然随着 $x$ 向右扫描，某些 $y$ 会逐渐变成非法，但是我们只需要在其 pop 或 cut 时对其重新检查，其余时间其无需检查，所以只会检查 $O(n)$ 次。
对于第三类转移，每次转移时需要找到每个空隙长度均小于 $\lfloor\frac{m-x}{2}\rfloor$ 的最远位置，需要在线段树上二分，找到后对线段树区间覆盖成合法状态，此类事件只会发生 $O(n)$ 次。每次得到新的 $minx_y=x$，对该位置允许第三类转移，并拆分一个空隙，可以用平衡树维护，此类事件同样只会发生 $O(n)$ 次。
最后我们需要维护一棵维护 DP 状态的线段树，一棵维护空隙长度的线段树，一棵维护有效位置的平衡树，一个单调栈。总时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。
记得开 long long 和多测清空。