#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

const int INF=0x3f3f3f3f;

const int MAXN=300;//点数的最大值

const int MAXM=5000;//边数的最大值

struct Node{

    int from,to,next;

    int cap;

}edge[MAXM];

struct Edge{

	int u,v,w;

}Tun[30],Acient[20],Modern[1000];

int tol;

int dep[MAXN];

int head[MAXN];

int val[MAXN];

void init(){

    tol=0;

    memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w){

    edge[tol].from=u;

    edge[tol].to=v; edge[tol].cap=w;  edge[tol].next=head[u];

    head[u]=tol++;

    edge[tol].from=v;

    edge[tol].to=u;

    edge[tol].cap=0;

    edge[tol].next=head[v];

    head[v]=tol++;

}

int BFS(int start,int end){

    int que[MAXN];

    int front,rear; front=rear=0;

    memset(dep,-1,sizeof(dep));

    que[rear++]=start;

    dep[start]=0;

    while(front!=rear){

        int u=que[front++];

        if(front==MAXN)front=0;

        for(int i= head[u];i!=-1; i=edge[i].next){

            int v=edge[i].to;

            if(edge[i].cap>0&& dep[v]==-1){

                dep[v]=dep[u]+1;

                que[rear++]=v;

                if(rear>=MAXN) rear=0;

                if(v==end)return 1;

            }

        }

    }

    return 0;

}

int dinic(int start,int end){

    int res=0;

    int top;

    int stack[MAXN];

    int cur[MAXN];

    while(BFS(start,end)){

        memcpy(cur,head, sizeof(head));

        int u=start;

        top=0;

        while(1){

            if(u==end){

                int min=INF;

                int loc;

               for(int i=0;i<top;i++)

                  if(min>edge [stack[i]].cap){

                      min=edge [stack[i]].cap;

                      loc=i;

                  }

                for(int i=0;i<top;i++){

                    edge[stack[i]].cap-=min;

                    edge[stack[i]^1].cap+=min;

                }

                res+=min;

                top=loc;

                u=edge[stack[top]].from;

            }

            for(int i=cur[u]; i!=-1; cur[u]=i=edge[i].next)

              if(edge[i].cap!=0 && dep[u]+1==dep[edge[i].to])

                 break;

            if(cur[u] !=-1){

                stack [top++]= cur[u];

                u=edge[cur[u]].to;

            }

            else{

                if(top==0) break;

                dep[u]=-1;

                u= edge[stack [--top] ].from;

            }

        }

    }

    return res;

}

int main(){

	int n,e;

	int nT,nA,nM;

	int u,v,w,p;

	while(scanf("%d%d",&n,&e)!=EOF){

		nT=nA=nM=0;

		for(int i=1;i<=n;i++)

			scanf("%d",&val[i]);

		for(int i=0;i<e;i++){

			scanf("%d%d%d%d",&u,&v,&w,&p);

			if(p==0){

				Modern[nM].u=u;Modern[nM].v=v;

				Modern[nM].w=w;

				nM++;

			}

			else if(p<0){

				Tun[nT].u=u;Tun[nT].v=v;

				Tun[nT].w=w;

				nT++;

			}

			else{

				Acient[nA].u=u; Acient[nA].v=v;

				Acient[nA].w=w;

				nA++;

			}

		}

		int Start=0,End;

		End=n+nT+1;

		int len=(1<<nA);

		int cost,people,ansc=0,anspeople=0;

		for(int i=0;i<len;i++){

			init();

			cost=0;

			for(int k=1;k<=n;k++){

				addedge(Start,k,val[k]);

			}

			for(int k=0;k<nA;k++){

				if(i&(1<<k)){

					addedge(Acient[k].u,Acient[k].v,INF);

					cost+=Acient[k].w;

				}

				else

				addedge(Acient[k].u,Acient[k].v,1);

			}

			for(int k=0;k<nM;k++){

				addedge(Modern[k].u,Modern[k].v,INF);

			}

			for(int k=0;k<nT;k++){

				addedge(Tun[k].u,n+k+1,INF);

				addedge(n+k+1,Tun[k].v,INF);

				addedge(n+k+1,End,Tun[k].w);

			}

		//	system("pause");

			people=dinic(Start,End);

			if(people>anspeople){

				anspeople=people;

				ansc=cost;

			}

			else if(people==anspeople){

				ansc=min(cost,ansc);

			}

		}

		if(anspeople==0){

			printf("Poor Heaven Empire\n");

		}

		else

		printf("%d %d\n",anspeople,ansc);

	}

	return 0;

}