#include <bits/stdc++.h>
using namespace std;
#define int long long
int answer = 1e9;
int c[40];
vector<int> g[40];
int n,m;
vector<int> route;
int done[40];
int wf[40][40];

int tl = 10000000;

void dfs(int x,int bit,int cost){

	if( done[x] ) return;
	int nextBit = bit;
	int diff = 0;
	if( !(bit >> x&1) ){
		diff += c[x];
		nextBit |= (1ll<<x);
	}

	for( auto i : g[x] ){
		if( !(bit >> i & 1) ){

			nextBit |= (1ll<<i);
			diff += c[i];
		}
	}
	int nextCost = cost + diff;
	if( nextCost >= answer ){
		return;
	}
	if( x == n - 1 ){
		answer = nextCost;
		return;
	}
	tl--;
	if( tl <= 0 ) return;
	done[x] = 1;
	route.push_back(x);
	//cout << "(" << nextBit << ")" << nextCost << " = ";
	//for( auto i : route) cout << i << " ";
	//cout << endl;
	
	random_shuffle(g[x].begin(),g[x].end());
	for( auto i : g[x] ){
		if( (bit >> i & 1) == 0 ) dfs(i,nextBit,nextCost);
	}
	route.pop_back();
	done[x] = 0;
}

signed main(){
	for(int i = 0 ; i < 40 ; i++)
		for(int j = 0 ; j < 40 ; j++)
			wf[i][j] = i == j ? 0 : 1e9;

	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		cin >> c[i];
	}


	for(int i = 0 ; i < m ; i++){
		int a,b;
		cin >> a >> b;
		--a,--b;
		g[a].push_back(b);
		g[b].push_back(a);
		//wf[a][b] = a;
		//wf[b][a] = b;
	}
	dfs(0,0,0);
	cout << answer << endl;


}
### Prompt

Create a solution in CPP for 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 int long long
int answer = 1e9;
int c[40];
vector<int> g[40];
int n,m;
vector<int> route;
int done[40];
int wf[40][40];

int tl = 10000000;

void dfs(int x,int bit,int cost){

	if( done[x] ) return;
	int nextBit = bit;
	int diff = 0;
	if( !(bit >> x&1) ){
		diff += c[x];
		nextBit |= (1ll<<x);
	}

	for( auto i : g[x] ){
		if( !(bit >> i & 1) ){

			nextBit |= (1ll<<i);
			diff += c[i];
		}
	}
	int nextCost = cost + diff;
	if( nextCost >= answer ){
		return;
	}
	if( x == n - 1 ){
		answer = nextCost;
		return;
	}
	tl--;
	if( tl <= 0 ) return;
	done[x] = 1;
	route.push_back(x);
	//cout << "(" << nextBit << ")" << nextCost << " = ";
	//for( auto i : route) cout << i << " ";
	//cout << endl;
	
	random_shuffle(g[x].begin(),g[x].end());
	for( auto i : g[x] ){
		if( (bit >> i & 1) == 0 ) dfs(i,nextBit,nextCost);
	}
	route.pop_back();
	done[x] = 0;
}

signed main(){
	for(int i = 0 ; i < 40 ; i++)
		for(int j = 0 ; j < 40 ; j++)
			wf[i][j] = i == j ? 0 : 1e9;

	cin >> n >> m;
	for(int i = 0 ; i < n ; i++){
		cin >> c[i];
	}


	for(int i = 0 ; i < m ; i++){
		int a,b;
		cin >> a >> b;
		--a,--b;
		g[a].push_back(b);
		g[b].push_back(a);
		//wf[a][b] = a;
		//wf[b][a] = b;
	}
	dfs(0,0,0);
	cout << answer << endl;


}
```