题意：

有n个地点，有g个人要去医院疗伤，他们最开始在in，在T时间内要到m个医院的某一个，有m条x到y的有向边，每条边每个单位时间可以通过pi人，走到这里需要ti个单位时间。

人可以停留在任意一个点，求最多能有多少人到达医院。

---

思路：

可以看出是一道最大流。

那么如何建图呢？

按时间拆点，比如n=4，t=5拆成：

超级源点向初始地点连边，容量为g，表示0时刻初始人数为g。

每个点的时刻向下个时刻连边，容量为INF/g，表示可以原地不动。

每个医院向超级汇点连边，容量为INF，表示一到医院就无限停留到汇点。

对于x到y的一条边，每个t的x向t+ti的y连边，容量为pi，表示在t时刻有pi个人可以从x到y，到达y的时间为t+ti。

其他就是要注意数组的大小。

每次做完网络流就觉得妙啊。

---

代码：

int s,e;
int top;
struct edge
{
    int to;
    int cap;
    int next;
}eg[10000100];
int head[200100];
int cur[200100];
int dis[200100];
void add(int x,int y,int z)
{
    eg[top].cap=z;
    eg[top].to=y;
    eg[top].next=head[x];
    head[x]=top++;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    queue<int>q;
    dis[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int id=q.front();
        q.pop();
        for(int i=head[id];i!=-1;i=eg[i].next)
        {
            int temp=eg[i].to;
            if(dis[temp]==-1&&eg[i].cap>0)
            {
                dis[temp]=dis[id]+1;
                q.push(temp);
                if(temp==e)break;
            }
        }
    }
    return dis[e]!=-1;
}
int dfs(int id,int cp)
{
    if(id==e||cp==0)return cp;
    int res=0,f;
    for(int i=cur[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(dis[temp]==dis[id]+1)
        {
            f=dfs(temp,min(cp-res,eg[i].cap));
            if(f>0)
            {
                eg[i].cap-=f;
                eg[i^1].cap+=f;
                res+=f;
                if(res==cp)return cp;
            }
        }
    }
    if(res==0)dis[id]=-1;
    return res;
}
int dinic()
{
    int ans=0;
    while(bfs())
    {
        for(int i=s;i<=e;i++)
            cur[i]=head[i];
        ans+=dfs(s,INF);
    }
    return ans;
}
int main()
{
    //freopen("/Users/apple/Downloads/problemset/testdata/A.in","r",stdin);
    int t,n,in,g,k,m,x,r,a,b,p,tt;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        scanf("%d%d%d",&in,&g,&k);
        top=0;
        memset(head,-1,sizeof(head));
        s=0;e=(k+1)*n+1;
        add(s,in,g);
        add(in,s,0);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d",&x);
            for(int i=0;i<=k;i++)
            {
                add(x+i*n,e,g);
                add(e,x+i*n,0);
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=0;j<k;j++)
            {
                add(i+j*n,i+(j+1)*n,g);
                add(i+(j+1)*n,i+j*n,0);
            }
        scanf("%d",&r);
        while(r--)
        {
            scanf("%d%d%d%d",&a,&b,&p,&tt);
            for(int i=0;i+tt<=k;i++)
            {
                add(a+i*n,b+(i+tt)*n,p);
                add(b+(i+tt)*n,a+i*n,0);
            }
        }
        printf("%d\n",min(dinic(),g));
    }
    return 0;
}