这题应该算是比较难的一道网络流的题，（但却在我校OJ考试上出现了），但是大家只要能理解此图的建边方式就行。
假设有5天的租车需求，虚拟出2*n+2 即 12个节点，0为源点，12为汇点。
1,源点到1 2 3 4 5流量为r[i],费用为0。6 7 8 9 10到汇点流量为r[i-n]，费用为0。
此题为一个检验能否满流且求满流花费最小的问题。
2，虚拟第2n+1个节点为买车途径，源点到2n+1节点花费为p[i],流量为c[i]，多重边。
3，对于每一个i+n节点，其来源有两个，一个是
2*n+1节点，即购买新车，一个是之前的车辆送去维修后的可用车辆。连接i和i+1节点，流量为INF，花费为0。
4，同时根据维修的天数
连接i和d[j]+i+1+n节点，花费为s[i]，流量为INF。
做完连边之后就跑一趟最小费用最大流模板，如最大流等于每天需要的车辆和，输出最小费用，否则，输出impossible。
#include<bits/stdc++.h>
using namespace std;
bool vis[400001];
int n,m,s,t,x,y,z,f,dis[400001],pre[400001],last[400001],flow[400001],maxflow,mincost,hh,hhh,ss,c,r,a[400001],b[400001];
struct Edge{
int to,next,flow,dis;
}edge[400001];
int head[400001],cnt;
queue <int> q;
void add(int from,int to,int flow,int dis)
{
edge[cnt].next=head[from];
edge[cnt].to=to;
edge[cnt].flow=flow;
edge[cnt].dis=dis;
head[from]=cnt++;
}
bool spfa(int s,int t)
{
memset(dis,0x7f,sizeof(dis));
memset(flow,0x7f,sizeof(flow));
memset(vis,0,sizeof(vis));
q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
while(!q.empty())
{
int now=q.front();
q.pop();
vis[now]=0;
for (int i=head[now]; i!=-1; i=edge[i].next)
{
if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)
{
dis[edge[i].to]=dis[now]+edge[i].dis;
pre[edge[i].to]=now;
last[edge[i].to]=i;
flow[edge[i].to]=min(flow[now],edge[i].flow);
if (!vis[edge[i].to])
{
vis[edge[i].to]=1;
q.push(edge[i].to);
}
}
}
}
return pre[t]!=-1;
}
void MCMF()
{
while(spfa(s,t))
{
int now=t;
maxflow+=flow[t];
mincost+=flow[t]*dis[t];
while(now!=s)
{
edge[last[now]].flow-=flow[t];
edge[last[now]^1].flow+=flow[t];
now=pre[now];
}
}
}
int read()
{
char ch=getchar();
int num=0;
while(ch<'0'||ch>'9')
{
ch=getchar();
}
while(ch<='9'&&ch>='0')
{
num=num*10+ch-'0';
ch=getchar();
}
return num;
}
int main()
{
hh=read();
hhh=hh;
while(hh--)
{
maxflow=0;
mincost=0;
printf("Case %d: ",hhh-hh);
ss=0;
cnt=0;
memset(head,-1,sizeof(head));
n=read();
c=read();
r=read();
t=2*n+1;
s=0;
for(int i=1;i<=n;i++)
{
if(i!=n)
{
add(i,i+1,99999999,0);
add(i+1,i,0,0);
}
}
for(int i=1;i<=n;i++)
{
x=read();
add(i,t,x,0);
add(t,i,0,0);
add(s,i+n,x,0);
add(i+n,s,0,0);
ss+=x;
}
for(int i=1;i<=c;i++)
{
x=read();
y=read();
add(s,1,x,y);
add(1,s,0,-y);
}
for(int i=1;i<=r;i++)
{
a[i]=read();
b[i]=read();
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=r;j++)
{
if(i+a[j]+1<=n)
{
add(n+i,i+a[j]+1,99999999,b[j]);
add(i+a[j]+1,n+i,0,-b[j]);
}
}
}
MCMF();
if(maxflow==ss)
{
printf("%d
",mincost);
}else{
puts("impossible");
}
}
}