#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 47;
const int MAXM = 4007;

struct eT
{
	void setd ( int _u, int _v, int _l )
	{
		u = _u, v = _v, last = _l;
	}

	int u, v, last;
}edge[MAXM];

int n, m;
int ans;
int a[MAXN];
int ke, la[MAXN];
int cc[MAXN];

void init ();
void input ();
void work ();

void srch ( int now, int na );



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%d", &n, &m );
	lpi ( i, 1, n ) scanf ( "%d", &a[i] );
	int u, v;
	ke = 0;
	INIT ( la, -1 );
	lp ( i, 0, m ){
		scanf ( "%d%d", &u, &v );
		edge[ke].setd ( u, v, la[u] );
		la[u] = ke++;
		edge[ke].setd ( v, u, la[v] );
		la[v] = ke++;
	}
}

void work ()
{
	// main work

	ans = INF;
	cc[1] = 1;
	srch ( 1, a[1] );

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



void srch ( int now, int na )
{
	if ( na >= ans ) return;
	if ( now == n ){
		for ( int i = la[now]; ~i; i = edge[i].last ) if ( !cc[edge[i].v] ) na += a[edge[i].v];
		ans = qmin ( ans, na );
		return;
	}

	int ta;
	ta = na;
	for ( int j = la[now]; ~j; j = edge[j].last ) if ( !cc[edge[j].v]++ ) ta += a[edge[j].v];

	for ( int i = la[now]; ~i; i = edge[i].last ){
		if ( cc[edge[i].v] == 1 ){
			srch ( edge[i].v, ta );
		}
	}

	for ( int j = la[now]; ~j; j = edge[j].last ) --cc[edge[j].v];
}
### Prompt

Generate a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 47;
const int MAXM = 4007;

struct eT
{
	void setd ( int _u, int _v, int _l )
	{
		u = _u, v = _v, last = _l;
	}

	int u, v, last;
}edge[MAXM];

int n, m;
int ans;
int a[MAXN];
int ke, la[MAXN];
int cc[MAXN];

void init ();
void input ();
void work ();

void srch ( int now, int na );



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%d", &n, &m );
	lpi ( i, 1, n ) scanf ( "%d", &a[i] );
	int u, v;
	ke = 0;
	INIT ( la, -1 );
	lp ( i, 0, m ){
		scanf ( "%d%d", &u, &v );
		edge[ke].setd ( u, v, la[u] );
		la[u] = ke++;
		edge[ke].setd ( v, u, la[v] );
		la[v] = ke++;
	}
}

void work ()
{
	// main work

	ans = INF;
	cc[1] = 1;
	srch ( 1, a[1] );

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



void srch ( int now, int na )
{
	if ( na >= ans ) return;
	if ( now == n ){
		for ( int i = la[now]; ~i; i = edge[i].last ) if ( !cc[edge[i].v] ) na += a[edge[i].v];
		ans = qmin ( ans, na );
		return;
	}

	int ta;
	ta = na;
	for ( int j = la[now]; ~j; j = edge[j].last ) if ( !cc[edge[j].v]++ ) ta += a[edge[j].v];

	for ( int i = la[now]; ~i; i = edge[i].last ){
		if ( cc[edge[i].v] == 1 ){
			srch ( edge[i].v, ta );
		}
	}

	for ( int j = la[now]; ~j; j = edge[j].last ) --cc[edge[j].v];
}
```