Problem: Example

Input

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2


Output

17

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
ll mask[41];
set<pair<ll,int> >used;
int n,m,a[41],ans,sum;
bool u[41];
void rec(ll zan,int cur,ll use){
	if(cur == n-1){
		ll M = 0; int S = 0;
		rep(i,n) if(((use>>i)&1LL)) M |= mask[i];
		rep(i,n) if(!((M>>i)&1LL)) S += a[i];
		ans = max(ans,S);
		return;
	}
	if(used.find(mp(use,cur)) != used.end()) return ;
	used.insert(mp(use,cur));
	rep(i,n){
		if(!((mask[cur]>>i)&1LL)) continue;
		if(!((zan>>i)&1LL)) continue;
		ll go = zan - (zan&mask[cur]);
		//assert(!((go>>i)&1LL));
		go += (1LL<<i);
		rec(go,i,use|(1LL<<i));
	}
}
int main(){
    cin>>n>>m;
    rep(i,n){
        cin>>a[i]; sum+=a[i];
        mask[i] = 1LL<<i;
    }
    rep(i,m){
        int a,b;
        cin>>a>>b; a--; b--;
        mask[a] |= 1LL<<b;
        mask[b] |= 1LL<<a;
    }
    queue<int>que;
    que.push(0);
    while(!que.empty()){
        int q = que.front(); que.pop(); if(u[q]) continue;
        u[q] = 1;
        rep(i,n) if( ((mask[q]>>i)&1LL) == 1LL && !u[i]){
            que.push(i);
        }
    }
    ll beg = 0;
    rep(i,n) if(u[i]) beg += 1LL<<i; 
    rec(beg,0,1);
    cout<<sum-ans<<endl;
}