#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int val[45];
LL use[45];
vector<int> s[45];
int ans=1<<30;
int n,m;
int cnt(LL mask){
    int tmp=0;
    for(int i=0;i<n;i++){
        if(mask & (1LL<<i)) tmp+=val[i];
    }
    return tmp;
}
LL is = 0;
void dfs(int u,int fa,LL mask){
    if(is & (use[u]^(1LL<<fa)^(1LL<<u))) return;
    if(u==n-1){
        ans=min(ans,cnt(mask));
        return;
    }
    for(int i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(is & (1LL << v)) continue;
        is ^= (1LL << v);
        dfs(v,u,mask | use[v]);
        is ^= (1LL << v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&val[i]);
        use[i] = (1LL << i);
    }
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x--, y--;
        s[x].push_back(y);
        s[y].push_back(x);
        use[x] |= (1LL << y);
        use[y] |= (1LL << x);
    }
    is=1;
    dfs(0,n,use[0]);
    printf("%d\n",ans);
}
### 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 <bits/stdc++.h>
using namespace std;
typedef long long int LL;
int val[45];
LL use[45];
vector<int> s[45];
int ans=1<<30;
int n,m;
int cnt(LL mask){
    int tmp=0;
    for(int i=0;i<n;i++){
        if(mask & (1LL<<i)) tmp+=val[i];
    }
    return tmp;
}
LL is = 0;
void dfs(int u,int fa,LL mask){
    if(is & (use[u]^(1LL<<fa)^(1LL<<u))) return;
    if(u==n-1){
        ans=min(ans,cnt(mask));
        return;
    }
    for(int i=0;i<s[u].size();i++){
        int v=s[u][i];
        if(is & (1LL << v)) continue;
        is ^= (1LL << v);
        dfs(v,u,mask | use[v]);
        is ^= (1LL << v);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&val[i]);
        use[i] = (1LL << i);
    }
    for(int i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        x--, y--;
        s[x].push_back(y);
        s[y].push_back(x);
        use[x] |= (1LL << y);
        use[y] |= (1LL << x);
    }
    is=1;
    dfs(0,n,use[0]);
    printf("%d\n",ans);
}
```