const int N = 1 << 15;

int f[N], g[N][26];

class Solution {

public:

    int n;

    string target;

    vector<string> strs;

    //target 最大 15. 也就是最多使用 15 个单词，每个单词出一个字母。

    // 所以极限值定为 20。

    const int INF = 20;

    // 将 字符 c 填充到状态 state

    int fill(int state, char c) {

        //v 表示状态 state 中添加了一个字母 c 之后的状态

        // 为什么需要 g？ 因为可能 不同的单词中有相同的字母

        // 遇到这种情况，可以直接返回，也就是下一步的剪枝。

        // 比如：当前状态 1101 遇到了字母 a，

        // 而在枚举下一个单词时候 1101 又遇到了 a，

        // 如果此时已经更新 (g [1101][a] 不等于初始值 - 1) 则直接返回即可。

        auto& v = g[state][c - 'a'];

        if (v != -1) return v; // 剪枝。

        v = state;

        // 枚举 target 的每一位。

        // （注意 target 的最大值也才 15，所以虽然 fill 操作频繁 但这一步并不慢）

        for (int i = 0; i < n; i ++ ) {

            //state >> i & 1 表示把 state 的二进制位的第 i 位拿出来

            // 因此，这个 if 表示如果状态 state 的第 i 位不是 1（或者说是 0）

            // 那么就判断，当前字符 c 是不是和它一样，如果一样就填进去。

            if (!(state >> i & 1) && target[i] == c) {

                // 把 v 的第 i 位变成 1，v 变成新的状态

                v += 1 << i;

                break; // 已经把 c 填充到 state 了 所以直接 break 就行

            }

        }

        return v;

    }

    // 爆搜

    int dfs(int state) {

        //v 表示当前状态下需要添加的单词数量

        auto& v = f[state];

        // 剪枝。如果 v 已经被计算过则直接返回

        if (v != -1) return v;

        // 如果状态为全 1, 说明搜索完毕，不需要添加任何单词了

        if (state == (1 << n) - 1) return v = 0;

        // 把 v 置为较大的数，如果最后 v 仍然是 INF，说明 v 从没真正有效更新过

        v = INF;

        // 枚举每个贴纸，也就是每个单词

        for (auto& str: strs) {

            int cur = state; //cur 临时保存当前状态。

            // 用单词的每个字母去填充当前状态。

            for (auto c: str) cur = fill(cur, c);

            // 填充完 如果和 填充前 不一样，说明状态有更新

            // 并且因为 目标是 最少使用的贴纸数量，所以这里用 min

            // cout << state << ' ';

            if (cur != state) {

                v = min(v, dfs(cur) + 1);

                // cout << v << ' ';

            }

        }

        return v;

    }

    int minStickers(vector<string>& stickers, string _target) {

        memset(f, -1, sizeof f);

        memset(g, -1, sizeof g);

        target = _target;

        strs = stickers;

        n = target.size();

        int res = dfs(0);

        // 如果所有的贴纸都不能满足目标，则返回 - 1；

        if (res == INF) res = -1;

        return res;

    }

};