---

比较裸的状压DP。

刚开始写麻烦惹...

\(f[i][s]\)表示考虑了前\(i\)家商店，所买物品状态为\(s\)的最小花费。

可以写求一遍一定去\(i\)商店的\(f[i]\)（\(f[i][s]=f[i-1][s]+dis[i]\)），然后再和不去\(i\)商店的\(f[i-1]\)取个\(\min\)。

复杂度是\(O(nm2^m)\)吗...

可以优化，处理\(f[s]\)表示在某家商店买\(s\)集合的物品的最小代价。然后令\(g[s]\)表示考虑所有商店买\(s\)集合的最小代价，有\(g[s]=\min(f[s],g[s']+f[s\ \text{xor}\ s'])\)。

复杂度\(O(n2^m+3^m)\)。

---

//27452kb   5284ms#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define lb(x) (x&-x)#define gc() getchar()typedef long long LL;const int N=103,M=16;int dis[N],cost[N][M+1],f[N][(1<
        
         <