#include <iostream>
    #include <string>
    #include <stdio.h>
    #include <stack>
    #include <algorithm>
    #include <list>
    #include <queue>
    #include <vector>
    #include <cassert>

using namespace std;

using std::string;
using std::cin;
using std::cout;
using std::list;
using std::endl;
using std::stack;
using std::queue;
using std::min;
using std::max;
using std::vector;

const int INF = 1000000000;
vector<char> symb = {'a', 'b', 'c', '.', '*', '+', '1'};
vector<char> ch = {'a', 'b', 'c'};

class Task8 {
public:
    using status = int;

    string s;
    char symbol;
    int k;

    Task8() :
        s(""),
        symbol('#'),
        k(0)
    {}

    Task8(string _s, char _c, int _k) :
        s(_s),
        symbol(_c),
        k(_k)
    {}

    string int2str(int x) { // x >= 0
        if (x == 0)
            return "0";
        string res = "";
        while (x > 0) {
            res += (char)(x % 10 + '0');
            x /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }

    struct State {
        vector<int> canMake;
        vector<int> minLen;

        State(int _k) :
            canMake(_k + 1, false),
            minLen(_k + 1, INF)
        {}

        State():
            canMake(0),
            minLen(0)
        {}
    };

    void read() {
        cin >> s;
        cin >> symbol;
        cin >> k;
    }

    status getArguments(vector<State>& stack, pair<State, State>& args) {
        if (stack.empty()) {
            return -1;
        }
        args.second = stack.back();
        stack.pop_back();

        if (stack.empty()) {
            return -1;
        }
        args.first = stack.back();
        stack.pop_back();

        return 1;
    }

    int solve() {
        vector<State> stack;

        for (char c : s) {
            if (c >= 'a' && c <= 'z') {
                stack.push_back(State(k));
                stack.back().minLen[0] = 1;
                if (c == symbol) {
                    stack.back().canMake[1] = 1;
                    stack.back().minLen[1] = 1;
                }
            } else if (c == '1') {
                stack.push_back(State(k));
                stack.back().canMake[0] = 1;
                stack.back().minLen[0] = 0;
            } else if (c == '+') {
                pair<State, State> args;
                if (getArguments(stack, args) == -1) {
                    return -1;
                }

                stack.push_back(State(k));
                for (int prefix = 0; prefix <= k; ++prefix) {
                    stack.back().canMake[prefix] = args.first.canMake[prefix] | args.second.canMake[prefix];
                    stack.back().minLen[prefix] = min(args.first.minLen[prefix], args.second.minLen[prefix]);
                }
            } else if (c == '.') {
                pair<State, State> args;
                if (getArguments(stack, args) == -1) {
                    return -1;
                }

                stack.push_back(State(k));
                for (int prefix = 0; prefix <= k; ++prefix) {
                    for (int takeFromFirst = 0; takeFromFirst <= prefix; ++takeFromFirst) {
                        int takeFromSecond = prefix - takeFromFirst;
                        stack.back().canMake[prefix] |= args.first.canMake[takeFromFirst] & args.second.canMake[takeFromSecond];

                        if (args.first.canMake[takeFromFirst]) {
                            stack.back().minLen[prefix] = min(
                                stack.back().minLen[prefix],
                                takeFromFirst + args.second.minLen[takeFromSecond]
                            );
                        }
                    }
                    stack.back().minLen[prefix] = min(
                        stack.back().minLen[prefix],
                        args.first.minLen[prefix] + args.second.minLen[0]
                    );
                }
            } else if (c == '*') {
                if (stack.empty()) {
                    return -1;
                }
                State arg = stack.back();
                stack.pop_back();

                stack.push_back(State(k));
                stack.back().canMake[0] = 1;
                for (int prefix = 1; prefix <= k; ++prefix) {
                    for (int i = 1; i <= prefix; ++i) {
                        if (arg.canMake[i] && stack.back().canMake[prefix - i]) {
                            stack.back().canMake[prefix] = 1;
                        }
                    }
                }

                stack.back().minLen[0] = 0;
                for (int prefix = 0; prefix <= k; ++prefix) {
                    for (int i = 0; i < prefix; ++i) {
                        if (stack.back().canMake[i]) {
                            stack.back().minLen[prefix] = min(
                                stack.back().minLen[prefix],
                                i + arg.minLen[prefix - i]
                            );
                        }
                    }
                }
            }
        }

        if ((int)stack.size() != 1) {
            return -1;
        }

        if (stack.back().minLen[k] == INF) {
            return INF;
        } else {
            return stack.back().minLen[k];
        }
    }
};


int ans (string str, char x, int k){
    if (x != 'a' && x != 'b' && x != 'c'){
        return -1;
    }
    stack<vector<int>> st;
    for (int i = 0; i < str.length(); ++i){
        if (str[i] != 'a' && str[i] == 'b' && str[i] == 'c' && str[i] != '1' && str[i] != '.' && str[i] != '*' && str[i] != '+'){
            return -1;
        }
        vector <int> min_length;
        if (str[i] == 'a' || str[i] == 'b' || str[i] == 'c' || str[i] == '1'){
            if (str[i] == x){
                min_length.push_back(1);
                min_length.push_back(1);
            }
            else{
                if (str[i] == '1'){
                    min_length.push_back(0);
                    min_length.push_back(INF);
                }
                else{
                    min_length.push_back(1);
                    min_length.push_back(INF);
                }
            }
            st.push(min_length);
        }
        if (str[i] == '+'){
            if (st.size() < 2){
                return -1;
            }
            vector<int> s2 = st.top();
            st.pop();
            vector<int> s1 = st.top();
            st.pop();
            int new_sz = max(s1.size(), s2.size());
            vector<int> new_vector;
            for (int j = 0; j < new_sz; ++j){
                new_vector.push_back(INF);
                if (s1.size() > j) new_vector[j] = min(s1[j], new_vector[j]);
                if (s2.size() > j) new_vector[j] = min(s2[j], new_vector[j]);
            }
            st.push(new_vector);
        }
        if (str[i] == '.'){
            if (st.size() < 2){
                return -1;
            }
            vector<int> s2 = st.top();
            st.pop();
            vector<int> s1 = st.top();
            st.pop();
            vector<int> new_vector(s1.size() + s2.size() - 1, INF);
            if (s2[0] < INF){
                for (int j = 0; j < s1.size(); ++j) {
                    if (s1[j] < INF) {
                        new_vector[j] = s1[j] + s2[0];
                    }
                }
            }
            for (int j = 0; j < s1.size(); ++j){
                if (s1[j] == j){
                    for (int l = 0; l < s2.size(); ++l){
                        if (s2[l] < INF){
                            new_vector[j + l] = min(new_vector[j + l], s1[j] + s2[l]);
                        }
                    }
                }
                if (j == 0 && s1[j] < INF && s2[0] < INF){
                    new_vector[0] = min(new_vector[0], s1[0] + s2[0]);
                }
            }
            st.push(new_vector);
        }
        if (str[i] == '*'){
            if (st.size() < 1){
                return -1;
            }
            vector<int> s1 = st.top();
            st.pop();
            vector<int> new_vector;
            new_vector.push_back(0);
            for (int j = 0; j < 2 * k; ++j){
                if (j + 1 < s1.size()) {
                    new_vector.push_back(s1[j + 1]);
                } else {
                    new_vector.push_back(INF);
                }
            }
            for (int j = 1; j <= 2 * k; ++j) {
                for (int l = 1; l < s1.size(); ++l) {
                    if (s1[l] < INF && new_vector[j - l] == (j - l)) {
                        new_vector[j] = min(new_vector[j], new_vector[j - l] + s1[l]);
                    }
                }
            }

            for (int j = new_vector.size() - 2; j >= 0; --j)
            {
                new_vector[j] = min(new_vector[j], new_vector[j + 1]);
            }
            st.push(new_vector);
        }
    }
    if (st.size() > 1){
        return -1;
    }
    vector<int> vec = st.top();
    if (k >= vec.size()){
        return INF;
    }
    return vec[k];
}

    void test()
    {
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 2) == 4);    // it's check answer for regex (acb + b(abc)*(ab + ba))*a
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 1) == 4);
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 3) == INF);
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'a', 1) == 1);
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'a', 2) == INF);
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'c', 1) == INF);
        assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 2) == 4);    // it's check answer for regex (acb + b(abc)*(ab + ba))*a
        assert(ans("ab+c.aba.*.bac.+.+*", 'c', 4) == INF);        // it's check answer for regex ((a + b)c + a(ba)*(b + ac))*
        assert(ans("ab+c.aba.*.bac.+.+*", 'c', 1) == INF);
        assert(ans("ab+c.aba.*.bac.+.+*", 'b', 1) == 2);
        assert(ans("ab+c.aba.*.bac.+.+*", 'b', 2) == INF);
        assert(ans("ab+c.aba.*.bac.+.+*", 'b', 3) == INF);
        assert(ans("ab+c.aba.*.bac.+.+*", 'a', 1) == 2);
        assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 5) == 5);  // it's check answer for regex aaa(ab + 1)*(1 + aaac)(aa)*
        assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 6) == 7);
        assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 7) == 7);
        assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 6) == 6);    // it's check answer for regex aaa(ab + 1)*(1 + aaac)(a)*
        assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 1) == 3);
        assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 3) == 3);
        assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'b', 1) == INF);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 1) == 2);         // // it's check answer for regex aa*bbb*cccc*
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 2) == 2);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 15) == 16);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 1) == 3);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 28) == 30);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 29) == 30);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 30) == 30);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 1) == 4);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 97) == 100);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 98) == 100);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 99) == 100);
        assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 100) == 100);


        assert(ans("ab+c.aba.*.bac.+.+*", 'a', 2) == 3);          // it's check answer for regex ((a + b)c + a(ba)*(b + ac))*
        assert(ans("ab+c.aba.*.bac.+.+*", 'a', 3) == INF);
        assert(ans("ab+c.aba.*.bac.+.+*", 'c', 4) == INF);
        assert(ans("aab..*aaaa...+", 'a', 2) == 3);               // it's check answer for regex (aab)* + aaaa
        assert(ans("aab..*aaaa...+", 'a', 4) == 4);
        assert(ans("ab+c.aba.*.bac.+.+*", 'y', 1) == -1);         // it's check answer for regex with not correct symbol x
        assert(ans("a**aa..aa.", 'a', 5) == -1);                  // it's check answer for regex a**aa aa (not correct regex
        // there are more than 1 elem in stack at the end)
        assert(ans("a**ad..aa.", 'a', 5) == -1);                  // it's check answer for not correct regex (there are not correct symbols)
        assert(ans("a1**aa..a0.", 'a', 5) == -1);                 // it's check answer for not correct regex (there are not correct symbols)
        assert(ans("*", 'a', 4) == -1);                           // it's check answer for not correct regex (where expected 1 elems for '*' but there are less)
        assert(ans("a**aa+++aa1...", 'b', 1) == -1);              // it's check answer for not correct regex (where expected 2 elems for '+' but there are less)
        assert(ans("a**1c+.bc*...", 'c', 1) == -1);               // it's check answer for not correct regex (where expected 2 elems for '.' but there are less)

    }

int testStrLen = 6;

void stress (vector<char> str) {
    if (str.size() == 9) {
        str.push_back('-');
        for (int i = 0; i < 2; ++i) {
            str[9] = ch[i];
            stress(str);
        }
    }
    else {
        if (str.size() == 10) {
            for (int i = 0; i < 50; ++i) {
                string s = "";
                for (int j = 0; j < 9; ++j) {
                    s += str[j];
                }
                int ansMy = ans(s, str[9], i);
                Task8 solver(s, str[9], i);
                int ansTrue =  solver.solve();
                if (ansMy != ansTrue) {
                    cout << "Wrong Answer! on test :  " << s << " " << str[9] << " " << i << endl;
                    cout << "My answer = " << ansMy << " True answer = " << ansTrue << endl;
                }
            }
        }
        else {
            str.push_back('-');
            for (int i = 0; i < 8; ++i) {
                str[str.size() - 1] = symb[i];
                stress(str);
            }
        }
    }
}

    int main() {
        string s;
        char x;
        int k;

        vector<char> str;
        stress(str);
        /*cin >> s >> x >> k;
        int answer = ans(s, x, k);
        if (answer == -1){
            cout << "Error : string of regular expression is not correct" << endl;
        }
        else {
            cout << "ans = " << answer << endl;
        } */
        test();
        /*for (int i = 0; i < 23; ++i) {
            cin >> s >> x >> k;
            int answer = ans(s, x, k);
            int waitAnswer;
            cin >> waitAnswer;
            if (answer != waitAnswer) {
                cout << "Wrong! On test " << i << endl;
            }
        }*/
        return 0;
    }