#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun Oct 11 23:22:41 JST 2020
 **/

template <class T> bool chmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T& a, const T& b) { return a < b ? a = b, true : false; }

const Int INF = 1e18;
signed main() {
    Int n, m;
    std::cin >> n >> m;
    std::vector<Int> w(n);
    REP(i, n) std::cin >> w[i];
    std::map<Int, Int> mp;
    mp[0] = 0;
    mp[INF] = INF;
    REP(i, m) {
        Int l, v;
        std::cin >> l >> v;
        dump(i, l, v, mp);
        if (v < *std::max_element(ALL(w))) {
            std::cout << -1 << std::endl;
            return 0;
        }
        while (1) {
            auto it = mp.lower_bound(v);
            if (it->second <= l) {
                mp.erase(it);
            } else {
                break;
            }
        }
        auto it = mp.upper_bound(v);
        if (it != mp.begin() && std::prev(it)->second >= l) continue;
        mp[v] = l;
    }
    dump(mp);
    Int ans = INF;
    std::sort(ALL(w));
    do {
        std::vector<Int> d(n);
        REP(i, 1, n) {
            Int sum = w[i];
            for (Int j = i - 1; j >= 0; j--) {
                sum += w[j];
                auto it = std::prev(mp.lower_bound(sum));
                chmax(d[i], d[j] + it->second);
            }
        }
        chmin(ans, d.back());
    } while (std::next_permutation(ALL(w)));
    assert(ans != INF);
    std::cout << ans << std::endl;
}

#include <bits/stdc++.h>
using namespace std;

# define endl "\n"
# define io_boost std::ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
typedef unsigned long long int ulli;
typedef long long int lli;
typedef unsigned int ui;

string X;
ulli M;

int main(){
    io_boost;
    cin >> X >> M;
    ulli d = 0, pos;
    reverse(X.begin(), X.end());
    for(int i = 0; i < X.size(); i++){
        d = max(d, ulli(X[i] - '0'));
        if(X[i] != '0') pos = i;
    }
    d++;
    if(X.size() == 1){
        if((X[X.size() - 1] - '0') > M) cout << 0 << endl;
        else cout << 1 << endl;
        return 0;
    }

    if(X[X.size() - 1] - '0' > M){
        cout << 0 <<endl;
        return 0;
    }


    ulli lo = 0, hi = M + 1;
    while(lo < hi){
        ulli mid = (lo + hi) / 2;
        ulli d = mid;
        ulli sum = 0;
        bool ok = true;
        ulli p = 1;
        for(int i = 0; i < X.size(); i++){
            sum += p * ulli(X[i] - '0');
            if(i < X.size() - 1){
                if(p > M / d){
                    ok = false;
                    break;
                }
            }
            if(p > M){
                ok = false;
                break;
            }
            if(sum > M){
                ok = false;
                break;
            }
            p *= d;
        }
        if(ok) lo = mid + 1;
        else hi = mid;
    }
    if(lo >= d + 1) cout << lo - d << endl;
    else cout << 0 << endl;
    return 0;
}