\(\text{Solution:}\)
经典模型（？） 来巩固一下
考虑移动的方案，必然是向上移动到某个等塔同一水平后再向右走。
那么，如果我们可以知道，在移动 \(x\) 步的情况下，所有海盗向右走的最短距离，那是不是就很好做了？
先考虑如何处理这个东西。枚举海盗和灯塔，那么 \(f_{|y-y_i|}=\max\{f,|x-x_i|\}\)
这是因为枚举了所有海盗在某一水平线的平移距离，直接取最大值即可。
那如何计算答案？考虑如果我们要移动 \(x\) 步往上走，那么我向右移动的距离必然要是移动 \(x\) 步以上的往右距离的最大值。
因为如果不移动这么多步，那一定可以被右上方一个点给全部遮住。
所以我们就可以直接倒序枚举记录最大值更新了。
注意到我们取了后缀最大值，所以有些点是不必要被 \(dp\) 到的。不行也可以直接在初始化的时候赋值为最小值即可。
枚举的时候，我们发现，枚举 \(n,m\) 是不可省的，但是能不能不枚举步数？因为最优的步数一定是跳跃到某个灯塔等高，所以可以直接去掉枚举高度的一维，这样就 \(O(nm)\) 了。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int INF=1e6+10;
int n,m;
struct pt{
int u,v;
}q[N],t[N];
int f[INF];
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
int vis[INF];
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d%d",&q[i].u,&q[i].v);
for(int i=1;i<=m;++i)scanf("%d%d",&t[i].u,&t[i].v);
int mx=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(q[i].v>t[j].v)continue;
int c=t[j].v-q[i].v;
mx=Max(mx,c);
f[c]=Max(f[c],Max(0,t[j].u-q[i].u+1));
}
}
int ans=mx+1;
int Mx=-1;
for(int i=mx;~i;--i){
Mx=Max(Mx,f[i]);
ans=Min(ans,Mx+i);
}
printf("%d\n",ans);
return 0;
}