#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <bitset>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int a[45];
vector <int> vec[45];
int n,m;
int best;
bitset <40> connect[45];

inline int getcost(bitset <40> bit)
{
	int res=0;
	for(int i=0;i<40;i++)
	{
		if(bit[i]) res+=a[i];
	}
	return res;
}

void dfs(int x,int cost,bitset<40> now)
{
//	if(cost!=getcost(now)) cout<<x<<' '<<cost<<' '<<now<<endl;
	int newcost=cost+getcost(connect[x] ^ (now & connect[x]));
	if(newcost>=best) return;
	if(x==n-1)
	{
		best=newcost;
		return;
	}
	bitset <40> t;
	for(int i=0;i<vec[x].size();i++)
	{
		if(now[vec[x][i]]) continue;
		dfs(vec[x][i],newcost,now | connect[x]);
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		connect[i][i]=true;
	}
	int x,y;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		x--;
		y--;
		vec[x].push_back(y);
		vec[y].push_back(x);
		connect[x][y]=true;
		connect[y][x]=true;
	}
	int cost=0;
	for(int i=0;i<n;i++)
	{
		if(connect[0][i]) cost+=a[i];
	}
	best=inf;
	dfs(0,0,0);
	cout<<best<<endl;
	return 0;
}

### Prompt

Your task is to create 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 <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <bitset>
#include <stack>
#define Endl endl
#define mp make_pair
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
#define ceil(a,b) ((a-1)/b+1)
#define srand() mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int a[45];
vector <int> vec[45];
int n,m;
int best;
bitset <40> connect[45];

inline int getcost(bitset <40> bit)
{
	int res=0;
	for(int i=0;i<40;i++)
	{
		if(bit[i]) res+=a[i];
	}
	return res;
}

void dfs(int x,int cost,bitset<40> now)
{
//	if(cost!=getcost(now)) cout<<x<<' '<<cost<<' '<<now<<endl;
	int newcost=cost+getcost(connect[x] ^ (now & connect[x]));
	if(newcost>=best) return;
	if(x==n-1)
	{
		best=newcost;
		return;
	}
	bitset <40> t;
	for(int i=0;i<vec[x].size();i++)
	{
		if(now[vec[x][i]]) continue;
		dfs(vec[x][i],newcost,now | connect[x]);
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		connect[i][i]=true;
	}
	int x,y;
	for(int i=0;i<m;i++)
	{
		cin>>x>>y;
		x--;
		y--;
		vec[x].push_back(y);
		vec[y].push_back(x);
		connect[x][y]=true;
		connect[y][x]=true;
	}
	int cost=0;
	for(int i=0;i<n;i++)
	{
		if(connect[0][i]) cost+=a[i];
	}
	best=inf;
	dfs(0,0,0);
	cout<<best<<endl;
	return 0;
}

```