#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<queue>

using namespace std;

typedef long long ll;

#define pb push_back

const ll INF=1e18;

const int inf=0x3f3f3f3f;

const int M=1e5+;

const int N=1e5+;

int a[M],head[M],cur[M],deep[M],s,t,tot,firnum,secnum,thnum;

struct node{

    int v,w,nextt;

}e[N];

struct Node{

    int u,v,w,cost;

}fir[M],sec[M],th[M];

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

    e[tot].v=v;

    e[tot].w=w;

    e[tot].nextt=head[u];

    head[u]=tot++;

    e[tot].v=u;

    e[tot].w=;

    e[tot].nextt=head[v];

    head[v]=tot++;

}

bool bfs(){

    for(int i=;i<=t;i++)

        deep[i]=;

    queue<int>que;

    que.push(s);

    deep[s]=;

    while(!que.empty()){

        int u=que.front();

        que.pop();

        for(int i=head[u];~i;i=e[i].nextt){

            int v=e[i].v;

            if(e[i].w>&&deep[v]==){

                deep[v]=deep[u]+;

                if(v==t)

                    return true;

                que.push(v);

            }

        }

    }

    return deep[t]==?false:true;

}

int dfs(int u,int fl){

    if(u==t)

        return fl;

    int x,res=;

    for(int i=cur[u];~i;i=e[i].nextt){

        int v=e[i].v;

        if(e[i].w>&&deep[v]==deep[u]+){

            x=dfs(v,min(fl-res,e[i].w));

            res+=x;

            e[i].w-=x;

            e[i^].w+=x;

            if(e[i].w)

                cur[u]=;

            if(res==fl)

                return fl;

        }

    }

    if(res==)

        deep[u]=;

    return res;

}

int dinic(){

    int res=;

    while(bfs()){

        for(int i=;i<=t;i++)

            cur[i]=head[i];

        res+=dfs(s,inf);

    }

    return res;

}

int n,ans,ansmin,mincost;

void init(){

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

    tot=;

    mincost=;

}

void solve(int now){

    init();

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

        addedge(s,i,a[i]);

    for(int i=;i<firnum;i++){

        addedge(fir[i].u,n++i,inf);

        addedge(n++i,fir[i].v,inf);

        addedge(n++i,t,fir[i].w);

    }

    for(int i=;i<secnum;i++){

        addedge(sec[i].u,sec[i].v,inf);

    }

    for(int i=;i<thnum;i++){

        if(now & (<<i) ){

            addedge(th[i].u,th[i].v,inf);

            mincost+=th[i].cost;

        }

        else

            addedge(th[i].u,th[i].v,);

    }

    int nowans=dinic();

    if(nowans > ans){

        ans = nowans;

        ansmin = mincost;

    }else if(nowans == ans){

        ansmin=min(ansmin,mincost);

    }

}

int main(){

    int m;

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

        ans=;

        ansmin=inf;

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

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

        }

        firnum=secnum=thnum=;

        s=;

        t=n+;

        for(int u,v,w,p,i=;i<=m;i++){

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

            if(p<){

                fir[firnum].u=u;

                fir[firnum].v=v;

                fir[firnum].w=w;

                firnum++;

                t++;

                //addedge(v,t,inf,0);

            }

            else if(p==){

                sec[secnum].u=u;

                sec[secnum].v=v;

                secnum++;

            }

            else{

                th[thnum].u=u;

                th[thnum].v=v;

                th[thnum].cost=w;

                thnum++;

            }

        }

        //cout<<firnum<<":"<<secnum<<":"<<thnum<<endl;

        for(int i=;i<=(<<thnum)-;i++)

            solve(i);

        if(ans==)

            puts("Poor Heaven Empire");

        else

            printf("%d %d\n",ans,ansmin);

        //puts("");

    }

    return ;

}