Untitled

#include 
#include 
#include 
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    string s;
    cin >> s;
    
    vector digits(10, false);
    for(int i = 0; i < (int) s.size(); i++) {
        digits[s[i] - '0'] = true;
    }
    int n;
    cin >> n;
    
    vector dp(5005, 1e9);
    
    for(int i = 0; i <= 5000; i++) {
        int tmp = i;
        bool ok = true;
        int cnt = 0;
        while(tmp > 0) {
            int digit = tmp % 10;
            if(!digits[digit]) {
                ok = false;
                break;
            }
            tmp /= 10;
            cnt++;
        }
        if(ok) {
            dp[i] = cnt;
        }
    }
    
  
    for(int i = 0; i <= 5000; i++) {
        for(int j = 0; j <= 5000; j++) {
                if(dp[i] != 1e9 and dp[j] != 1e9) {
                    dp[min(i * j, 5000)] = min(dp[min(i * j, 5000)], dp[i] + dp[j] + 1);
                }
            
        }
    }
    for(int i = 0; i <= 5000; i++) {
        for(int j = 0; j <= 5000; j++) {
        
            if(dp[i] != 1e9 and dp[j] != 1e9) {
                dp[min(i + j, 5000)] = min(dp[min(i + j, 5000)], dp[i] + dp[j] + 1);
            }
        }
    }
    cout << dp[n] << endl;

    return 0;
}
/*
 5 2 2
 0 1 1 0 1
 0 1
1 1
 
 13 4 3
 1 1 3 2 0 1 2 0 0 0 0 3 1
 0 2
 2 1
 1 2
 
 5 3 1
 1 2 0 1 2
 0 2
 **/