During the world war, to avoid the upcoming Carpet-bombing from The Third Reich, people in Heaven Empire went to Great Tunnels for sheltering.
There are N cities in Heaven Empire, where people live, with 3 kinds of directed edges connected with each other. The 1st kind of edges is one of Great Tunnels( no more than 20 tunnels) where a certain number of people can hide here; people can also go through
one tunnel from one city to another. The 2nd kind of edges is the so-called Modern Road, which can only let people go through. The 3rd kind of edges is called Ancient Bridge and all the edges of this kind have different names from others, each of which is
named with one of the twelve constellations( such as Libra, Leo and so on); as they were build so long time ago, they can be easily damaged by one person's pass. Well, for each bridge, you can spend a certain deal of money to fix it. Once repaired, the 3rd
kind of edges can let people pass without any limitation, namely, you can use one bridge to transport countless people. As for the former two kinds of edges, people can initially go through them without any limitation.
We want to shelter the most people with the least money.
Now please tell me the largest number of people who can hide in the Tunnels and the least money we need to spend to realize our objective.

Multiple Cases.
The first line, two integers: N (N<=100), m (m<=1000). They stands for the number of cities and edges.
The next line, N integers, which represent the number of people in the N cities.
Then m lines, four intergers each: u, v, w, p (1<=u, v<=N, 0<=w<=50). A directed edge u to v, with p indicating the type of the edge: if it is a Tunnel then p < 0 and w means the maximum number people who can hide in the the tunnel; if p == 0 then it is a Modern
Road with w means nothing; otherwise it is an Ancient Bridge with w representing the cost of fixing the bridge. We promise there are no more than one edge from u to v.

If nobody can hide in the Tunnels, print “Poor Heaven Empire”, else print two integers: maximum number and minimum cost.

4 4
2 1 1 0
1 2 0 0
1 3 0 0
2 4 1 -1
3 4 3 -1

4 4
2 1 1 0
1 2 0 0
1 3 3 1
2 4 1 -1
3 4 3 -1

4 0
4 3
 
#include<iostream>
#include<cstdio>
#include<algorithm> 

using namespace std;

#define mm(a) memset((a),0,sizeof((a)))
#define INF 0x3FFFFF
#define MAXN 150
#define MAXM 5000

struct node
{
	int to,c;
	int next;
}e[MAXM];

struct troad
{
    int u,v;
    int cost;
    bool deleted;
}ee[100];


int u[MAXM],v[MAXM],w[MAXM],p[MAXM],g[MAXN];
int n,m,een,en,dis[MAXN],gap[MAXN];
int pp[MAXN];
int st,ed;
int maxflow,mins;
int counts;

void add(int a,int b,int c)
{
	e[en].to=b;
	e[en].c=c;
	e[en].next=g[a];
	g[a]=en++;
	e[en].to=a;
	e[en].c=0;  
	e[en].next=g[b];
	g[b]=en++;	
}

int sap(int u,int flow)
{
	if(u==ed)
		return flow;
	int ans=0,i,t;
	for(i=g[u];i!=-1;i=e[i].next)
	{
		if( e[i].c && dis[u]==dis[e[i].to]+1)
		{
			t=sap(e[i].to,min(flow-ans,e[i].c));
			e[i].c-=t,e[i^1].c+=t,ans+=t;
			if(ans==flow)
				return ans;
		}
	}
	if(dis[st]>=n+counts+2)
		return ans;
	if(!--gap[dis[u]])  
		dis[st]=n+counts+2;
	++gap[++dis[u]];
	return ans;
}

int build()
{
    int ans=0;
    counts=0;
    en=0; 
    memset(g,-1,sizeof(g));
    for(int i=1;i<=n;i++)
        add(st,i,pp[i]);
    for(int i=1;i<=m;i++)
    {
        if(p[i]<0)
        {
            add(u[i],n+1+counts,INF);
            add(n+1+counts,v[i],INF);
            add(n+1+counts,ed,w[i]);
            add(u[i],v[i],INF);
            counts++;
        }
        if(p[i]==0)
            add(u[i],v[i],INF);
        if(p[i]>0)
            continue;
    }
    for(int i=0;i<een;i++)
    {
        if(!ee[i].deleted)
        {
            add(ee[i].u,ee[i].v,INF);
            ans+=ee[i].cost;
        }
        else
        {
			add(ee[i].u,ee[i].v,1); //审题要仔细，不修的桥只能过一个人而不是不能过人，因为这里wa了很多次 
		}
    }
    return ans;
}

void solve()
{
	st=0,ed=133;
	int ans=0;
    een=0;
	int temp;
	for(int i=1;i<=n;i++)
	   scanf("%d",&pp[i]);
	for(int i=1;i<=m;i++)
	{
        scanf("%d%d%d%d",&u[i],&v[i],&w[i],&p[i]);
        if(p[i]>0)
        {
            ee[een].u=u[i];
            ee[een].v=v[i];
            ee[een].cost=w[i];
            ee[een++].deleted=false;
        }
    }
    mins=build();  //先要求一次最大流，求出最大避难人数，接下来的枚举要和这个值比较 
    mm(gap),mm(dis);
    for(gap[0]=n+counts+2;dis[st]<n+counts+2;)
		ans+=sap(st,INF);
	maxflow=ans;
	if(maxflow==0)
	{
		printf("Poor Heaven Empire\n");
		return ;
	}
	while(1)    
	{
        int tempmin=mins;
        int tag=-1;
        for(int i=0;i<een;i++)  //每次循环去一条弧，如果最大流不变，费用变少则记录，选出减少量最大的弧，直到选不出来为止 
         {
            if(!ee[i].deleted)
            {
                int tt;
                ee[i].deleted=true;
                tt=build();   //重新建图 
                mm(gap),mm(dis);
                ans=0;
                for(gap[0]=n+counts+2;dis[st]<n+counts+2;)
		              ans+=sap(st,INF);
		        if(ans==maxflow && tt<tempmin)
		        {
                    tag=i;
                    tempmin=tt;
                }
                ee[i].deleted=false;  
            } 
        }
        if(tag==-1)   //所有能删除的点都已经删除，跳出循环 
            break;
        ee[tag].deleted=true;   //删除边 
        mins=tempmin;   //更新花费 
    }
    if(maxflow==0)
        printf("Poor Heaven Empire\n");  //其实这句放在这里已经没有意义了，但不影响效率，不去管它了 
	else
        printf("%d %d\n",maxflow,mins);
    
}

int main()
{
	while(scanf("%d%d",&n,&m)!=EOF) solve();
	return 0;
}