题面传送门
指导居然卡空间差评！！！！
首先肯定可以暴力建图然后跑费用流，每次增加一个流量，这样可以\(O(n^2m)\)
然后发现如果一行是一个连续没有障碍段那么肯定走到最后再换行一定不会更劣。
所以可以这样缩点，并把每个点拆成出点和入点限流，然后对于每个障碍点连出\(m\)条边即可。
时间复杂度\(O(n^2k)\)
但是spfa在网格图中表现并不好，加上SLF+swap才勉强卡过。
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define lb long db
#define N 5000
#define M 500000
#define mod 1000000007
#define eps (1e-4)
#define U unsigned int
#define it iterator
#define Gc() getchar()
#define Pc(x) putchar(x) 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (m*(x-1)+(y))
using namespace std;
int n,m,k,q,z,x,y,S,T,S1,Fs[N+5],F[N+5],pre[N+5],d[N+5],G[N+5],g[N+5],cnt,p,Fl[N+5];vector<int>Id[N+5],In[N+5],Out[N+5];
struct yyy{int to,w,g,z;}tmp;struct ljb{int head,h[N+5];yyy f[M+5];I void add(int x,int y,int w,int g){f[head]=(yyy){y,w,g,h[x]};h[x]=head++;}}s;
I void Get(int x,int y,int w,int g){/*printf("%d %d %d %d\n",x,y,w,g);*/s.add(x,y,w,g);s.add(y,x,-w,0);}deque<int> Q;
I void Make(){if(Q.size()<2) return;int now1=Q.front(),now2=Q.back();if(d[now1]<d[now2])return;Q.pop_front();Q.pop_back();Q.push_front(now2);Q.push_back(now1);}
I int bfs(){
	re int i;re yyy tmp;/*int cnt=0;*/Q.push_front(S);Me(d,0x3f);Me(g,0);d[S]=0;g[S]=1e9;while(!Q.empty()){
		/*cnt++;*/z=Q.front();Q.pop_front();Make();Fl[z]=0;for(int i=s.h[z];~i;i=tmp.z){
 			/*cnt++;*/tmp=s.f[i];if(!tmp.g||d[tmp.to]<=d[z]+tmp.w)continue;d[tmp.to]=d[z]+tmp.w;g[tmp.to]=min(g[z],tmp.g);pre[tmp.to]=i;!Fl[tmp.to]&&(((Q.empty()||d[tmp.to]<=d[Q.front()])?Q.push_front(tmp.to):Q.push_back(tmp.to)),Make(),Fl[tmp.to]=1);
		}
	}/*printf("%d\n",cnt);*/return d[T]<1e9;
}
I int find(int x,int y){int p=upper_bound(Id[x].begin(),Id[x].end(),y)-Id[x].begin()-1;if(Id[x][p]==y) return -1;else return p;}
int main(){
//	freopen("lord.in","r",stdin);freopen("lord.out","w",stdout);
	re int i,j,h;Me(F,0x3f);Me(s.h,-1);scanf("%d%d%d%d",&n,&m,&k,&q);for(i=1;i<=n;i++) Id[i].push_back(0),Id[i].push_back(m+1);for(i=1;i<=k;i++) scanf("%d%d",&x,&y),Id[x].push_back(y);
	for(i=1;i<=n;i++) {
		sort(Id[i].begin(),Id[i].end());for(j=0;j<Id[i].size()-1;j++) In[i].push_back(Id[i][j]^(Id[i][j+1]+1)?++cnt:0),Out[i].push_back(Id[i][j]^(Id[i][j+1]+1)?++cnt:0);
	}S1=0;S=cnt+1;T=cnt+2;for(i=1;i<=n;i++){
		In[i][0]&&(Get(S1,In[i][0],0,1),0),Out[i][Out[i].size()-1]&&(Get(Out[i][Out[i].size()-1],T,0,1),0);for(j=0;j<In[i].size();j++) In[i][j]&&(Get(In[i][j],Out[i][j],0,1),0);
	}
	for(i=1;i<=n;i++){
		for(j=0;j<In[i].size()-1;j++){
			for(h=i-1;h;h--){
				p=find(h,Id[i][j+1]-1);if(p==-1) break;p=find(h,Id[i][j+1]),~p&&(Get(Out[i][j],In[h][p],i-h,1)/*,printf("%d %d %d %d\n",i,Id[i][j],h,Id[h][p+1])*/,0);
			}for(h=i+1;h<=n;h++){
				p=find(h,Id[i][j+1]-1);if(p==-1) break;p=find(h,Id[i][j+1]),~p&&(Get(Out[i][j],In[h][p],h-i,1)/*,printf("%d %d %d %d\n",i,Id[i][j],h,Id[h][p+1])*/,0);
			}
		}
    }F[0]=0;Get(S,S1,0,0);for(i=1;i<=n;i++){
		s.f[s.head-2].g++;F[i]=F[i-1];G[i]=G[i-1];while(bfs()){
			F[i]+=g[T]*d[T];G[i]+=g[T];x=T;while(x^S) s.f[pre[x]].g-=g[T],s.f[pre[x]^1].g+=g[T],x=s.f[pre[x]^1].to;
		}if(G[i]<i){F[i]=1e9;break;}
	}while(q--) scanf("%d",&x),printf("%d\n",upper_bound(F+1,F+n+1,x)-F-1);
}