D - Separation and Union

#include <bits/stdc++.h>

#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)

#define srep(i,a,b) for(int i = a; i < b; i++) //[a,b)

#define all(A) (A).begin(),(A).end()

#define rall(A) (A).rbegin(),(A).rend()

#define pmt(A) next_permutation(all(A))

using namespace std;

using ll = long long;

using ull = unsigned long long;

using P = pair<ll,ll>;

using pq = priority_queue<P,vector<P>,greater<P>>;

const ll inf = 8e18;

const int iinf = (int)1e9;

const int mod9 = 998244353;

const int mod1 = 1000000007;

struct Edge { int to; ll cost; int from; };

bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }

using Graph = vector<vector<int>>;

using SGraph = vector<set<ll>>;

template <typename T>

int siz(T& a){return (int)a.size();}

​

int main(void){

    string s; cin >> s;

    int n; cin >> n;

    vector<string> T(n); rep(i,n) cin >> T[i];

​

    vector<int> as(26,0);

    rep(i,siz(s)) as[s[i]-'a']++;

​

    int ans = iinf;

    for(int b = 1; b < (1<<n); b++){

        vector<int> at(26,0);

        int now = 0;

        rep(i,n){

            if(b & (1<<i)){

                rep(j,siz(T[i])) at[T[i][j]-'a']++;

                now++;

            }

        }

        bool ok = 1;

        rep(i,26) if(as[i] > at[i]) ok = 0;

        if(ok) ans = min(ans,now);

    }

​

    cout << (ans == iinf ? -1 : ans);

}

​

from itertools import product

​

S = input()

N = int(input())

​

T = list(input().split())

​

alpS = [0 for i in range(26)]

for s in S:

    alpS[ord(s)-97] += 1

​

ans = N+1

for p in product((0,1),repeat = N):

    alpT = [0 for i in range(26)]

    now = 0

    for i in range(N):

        if p[i] == 1:

            for c in T[i]:

                alpT[ord(c)-97] += 1

            now += 1

    ok = True

    for i in range(26):

        if alpT[i] < alpS[i]:

            ok = False

    if ok == True:

        ans = min(ans,now)

​

print(-1 if ans == N+1 else ans)

​