#include<iostream>
using namespace std;
char va[1000][1000]={};//R
int vb[1000]={},ia,ib,ic,id;//vb=Cost,vc=Row_Count
string sa;
struct ta_t
{
int cost,weight;
string result,choice;
};
ta_t best_ta={2147483647,0,"",""};
string fa(string sa,int fia)
{
for(int i=0;i<ia;i++)
if(sa[i]=='1' || va[i][fia]==1)sa[i]='1';
return sa;
}
void fb(ta_t ta,int fia)
{
ta_t tb={ta.cost+1,ta.weight+vb[fia],ta.result,ta.choice};
tb.result=fa(tb.result,fia);
tb.choice[fia]='1';
bool ba=true;
for(int i=0;ba && i<ia;i++)
if(tb.result[i]=='0')ba=false;
if(ba)
{
if(tb.cost<best_ta.cost || (tb.cost==best_ta.cost && tb.weight<best_ta.weight))
best_ta=tb;
return;
}
for(int i=fia+1;tb.cost<=best_ta.cost && i<ib;i++)
if(tb.choice[i]=='0')fb(tb,i);
}
void fc(ta_t ta,int fia)
{
ta_t tb={ta.cost+1,ta.weight+vb[fia],ta.result,ta.choice};
tb.result=fa(tb.result,fia);
tb.choice[fia]='1';
bool ba=true;
for(int i=0;ba && i<ia;i++)
if(tb.result[i]=='0')ba=false;
if(ba)
{
if(tb.cost==best_ta.cost && tb.weight==best_ta.weight)
{
for(int i=0;i<ib;i++)
if(tb.choice[i]=='1')printf("%d ",i+1);
printf("\n");
}
return;
}
for(int i=fia+1;tb.cost<=best_ta.cost && i<ib;i++)
if(tb.choice[i]=='0')fc(tb,i);
}
int main(int argc,char* argv[])
{
if(argc!=2)return 0;
FILE* fin=fopen(argv[1],"r");
fscanf(fin,"%d %d",&ia,&ib);
for(int i=0;i<ib;i++)
fscanf(fin,"%d",&vb[i]);
while(fscanf(fin,"%d %d",&ic,&id)!=EOF)
va[ic-1][id-1]=1;
/*
for(int i=0;i<ia;i++)
for(int j=0;j<ib;j++)
printf("%d%s",va[i][j],((j!=ib-1)?" ":"\n"));
*/
for(int i=0;i<ia;i++)sa+="0";
ta_t ta1={0,0,sa,sa};
for(int i=0;i<ib;i++)fb(ta1,i);
for(int i=0;i<ib;i++)fc(ta1,i);
printf("(%d,%d)\n",best_ta.cost,best_ta.weight);
system("pause");
}