**题意：

     给以三种有向边

    （1） 隧道，可以过无数人，也可以藏c个人。

    （2） 路，只能过人（流量INF）。

    （3）古桥，如果不修理可以过1个人，修理可以过无数个人，但是要花费c那么多钱 同时还给了每个城市的人数，要求是城市的人去隧道里躲避，问你在躲避人数最多的前提下费用最小，费用就是修理古桥所用的钱。

思路：

       先看古桥数量，最多12个，2^12 也就四千多，直接二分枚举哪些古桥是修理的，然后对于每一种状态，我们都重新建图，用最大流去找最多藏多少人，然后更新最优就行了。下面说下建图吧，这个题目的建图不难，直接建就行。

 (0)建立超级远点和汇点，s,t。

 (1)隧道，既然可以藏人，就可以虚拟出一个点来，比如给的隧道a(点),b(点),c(人数)

我们可以虚拟出来一个点d，add(a ,d ,INF),add(d ,b ,INF) ,add(d ,t ,c);

 (2)路,这个没话说 add(a ,b ,INF);
**

(3)古桥，对于深搜的当前状态的当前这个古桥，如果是修理add(a ,b ,INF),如果不是修理add(a ,b ,1)这样一边重建，一边深搜更新最大值就行了。

#include
#include
#include

#define N_node 500
#define N_edge 10000
#define INF 1000000000
using namespace std**;

typedef struct
{
int** to ,next ,cost; }STAR**;

typedef struct
{
int** a ,b ,c; }NODE**;

typedef struct
{
int** x ,t; }DEP;

STAR E[N_edge];
NODE L[1100] ,G[15] ,S[25]; int n1 ,n2 ,n3;
DEP xin ,tou; int list[N_node] ,tot; int list1[N_node]; int deep[N_node]; int mk[15]; int pp[1100**];

void** add(int a ,int b ,int c) {
E[++tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;

E[++tot].to = a;
E[tot].cost = 0;
E[tot].next = list[b];
list[b] = tot**;
}

int** minn(int x ,int y) { return x < y ? x : y**;
}

bool** BFS_Deep(int s ,int n ,int t) {
memset(deep ,255 ,sizeof(deep));
deep[s] = 0;
xin.x = s ,xin.t = 0;
queue<DEP>q;
q.push(xin); while(!q.empty()) {
tou = q.front();
q.pop(); for(int k = list[tou.x] ;k ;k = E[k].next) {
xin.x = E[k].to;
xin.t = tou.t + 1; if(deep[xin.x] != -1 || !E[k].cost) continue;
deep[xin.x] = xin.t;
q.push(xin); } } for(int i = 0 ;i <= n ;i ++)
list1[i] = list[i]; return deep[t] != -1**;
}

int** DFS_flow(int s ,int t ,int flow) { if(s == t) return flow; int nowflow = 0; for(int k = list1[s] ;k ;k = E[k].next) {
list1[s] = k; int to = E[k].to; int c = E[k].cost; if(deep[to] != deep[s] + 1 || !c) continue; int tmp = DFS_flow(to ,t ,minn(c ,flow - nowflow));
nowflow += tmp;
E[k].cost -= tmp;
E[k^1].cost += tmp; if(flow == nowflow) break; } if(!nowflow) deep[s] = 0; return nowflow**;
}

int** DINIC(int s ,int t ,int n) { int ans = 0; while(BFS_Deep(s ,t ,n)) {
ans += DFS_flow(s ,t ,INF); } return ans**;
}

void** Rebuid(int n) {
memset(list ,0 ,sizeof(list)) ,tot = 1; int T = n + n1 + 1; for(int i = 1 ;i <= n1 ;i ++) { int a = S[i].a ,b = S[i].b ,c = S[i].c;
add(i + n ,T ,c);
add(a ,i + n ,INF) ,add(i + n ,b ,INF); } for(int i = 1 ;i <= n2 ;i ++)
add(L[i].a ,L[i].b ,INF); for(int i = 1 ;i <= n3 ;i ++) if(mk[i]) add(G[i].a ,G[i].b ,INF); else add(G[i].a ,G[i].b ,1); for(int i = 1 ;i <= n ;i ++)
add(0 ,i ,pp[i**]);
}

int** Min_C ,Max_F; void DFS(int s ,int t ,int ii ,int nowcost ,int n) { if(ii == n3 + 1) {
Rebuid(n); int now = DINIC(s ,t ,t); if(Max_F < now || Max_F == now && Min_C > nowcost) {
Max_F = now;
Min_C = nowcost; } return ; }
mk[ii] = 1;
DFS(s ,t ,ii + 1 ,nowcost + G[ii].c ,n);
mk[ii] = 0;
DFS(s ,t ,ii + 1 ,nowcost ,n**);
}

int main ()
{
int** n ,m ,i ,q; while(~scanf("%d %d" ,&n ,&m)) { for(i = 1 ;i <= n ;i ++)
scanf("%d" ,&pp[i]);
n1 = n2 = n3 = 0;
NODE A; for(i = 1 ;i <= m ;i ++) {
scanf("%d %d %d %d" ,&A.a ,&A.b ,&A.c ,&q); if(q < 0) S[++n1] = A; if(!q) L[++n2] = A; if(q > 0) G[++n3] = A; }
Min_C = Max_F = 0;
DFS(0 ,n + n1 + 1 ,1 ,0 ,n); if(!Max_F) puts("Poor Heaven Empire"); else printf("%d %d\n" ,Max_F ,Min_C); } return 0; }