Pre knowledge ：

Pressure ：

In binary （ or n Base number ） Represents the decimal number to represent the State , State adjustment through bit operation .
for instance , In the room 4 The light turns on and off as 0101, The decimal number stored in this state is 5.

Numbered from right to left 0,1,2,3. Open the first 3 The lamp is about to be in its original state 5 Turn into 5|(1<<3).
Only a brief introduction is made to the shape pressure .

Enumerate binary subsets ：

Binary numbers are s, Enumerating its subsets means , Enumerate all x∈{x| x|s=s}.
The specific operation is as follows ：

for (int i = s; i; i = (i - 1) &ｓ)

In this way, we can accurately enumerate s Binary subset of , Note that the neutron set of the cycle body does not contain 0（ An empty set ）, To add , Cycle conditions need to be set manually .

Text ：

summary ：

seeing the name of a thing one thinks of its function , A subset of dp State transition of , It is usually transferred from the subset to the current set , With the enumeration method of enumerating binary subsets , The code will be very comfortable to write , Can have better complexity .

frame ：

Transfer equation dp[S]=dp[S⊕T]+max(dp[T]),T⊆S And T≠Ø For example , among S⊕T The meaning is T About S The complement of , The general framework is as follows .

for(int i=0;i<1<<n;i++)
{
    
	for(int j=S&(S-1);j;S&(j-1))
	{
    
		dp[S]=max(dp[S],dp[S^j]+dp[j]);
	}
}

Proof of complexity ：

Enumerate subsets of all collections .
${\sum }_{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)2^i=3^n$
That is to say o(3ⁿ).

Example （ The bullock practice match 49B）：

A brief description of the problem ： this is it

AC Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;

int p[20];
int plan[1<<20];
int dp[1<<20];

int num[1<<20];
int gt(int x)
{
    
    if(x==0)return 0;
    if(num[x])return num[x];
    int ans=0;
    int t=x;
    while(t!=0)
    {
    
        ans++;
        t-=t&-t;
    }
    return num[x]=ans;
}

int main()
{
    
    int n,m;
    scanf("%d%d",&n,&m);
    int sum=0;
    for(int i=0;i<n;i++)scanf("%d",&p[i]),sum+=p[i];
    sort(p,p+n,greater<int>());
    for(int i=1;i<=m;i++)
    {
    
        int tn;
        scanf("%d",&tn);
        int x=0;
        for(int j=1;j<=tn;j++)
        {
    
            int w;
            scanf("%d",&w);
            x|=1<<w-1;
        }
        plan[x]=1;
    }
    dp[0]=0;
    for(int i=1;i<1<<n;i++)
    {
    
        for(int j=i&(i-1);1;j=i&(j-1))
        {
    
            int e=0;
            if(plan[i^j])e=p[gt(i)-1];
            else e=0;
            dp[i]=max(dp[i],dp[j]+e);
            if(j==0)break;
        }
    }
    printf("%d\n",sum-dp[(1<<n)-1]);
    return 0;
}