using namespace std;
using vi = vector<int>;
int const NMAX = 1e3 + 11;
int n, m, c, w[NMAX], b[NMAX], rep[NMAX], cur_rep;
bool visited[NMAX];
vi g[NMAX], component;
inline pair<int, int> add_pair(pair<int, int> a, pair<int, int> b)
{
    return make_pair(a.first + b.first, a.second + b.second);
}
pair<int, int> dfs(int u, int p = -1)
{
    pair<int, int> tbw = {b[u], w[u]};
    rep[u] = cur_rep;
    visited[u] = true;
    for (auto v : g[u])
    {
        if (v == p or visited[v])
            continue;
        tbw = add_pair(dfs(v, u), tbw);
    }
    component.push_back(u);
    return tbw;
}
int solve(void)
{
    vector<vi> dp(n + 1, vi(c + 1, 0));
    for (int u = 1; u <= n; ++u)
    {
        if (visited[u])
            continue;
        ++cur_rep;
        auto [tb, tw] = dfs(u);
        for (int cap = 0; cap <= c; ++cap)
        {
            auto &ans = dp[cur_rep][cap];
            ans = max(ans, dp[cur_rep - 1][cap]);
            if (cap - tw >= 0)
                ans = max(ans, dp[cur_rep - 1][cap - tw] + tb);
            for (auto v : component)
                if (cap - w[v] >= 0)
                    ans = max(ans, dp[cur_rep - 1][cap - w[v]] + b[v]);
        }
        component.clear();
    }
    return dp[cur_rep][c];
}
int main(void)
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int u, v;
    cin >> n >> m >> c;
    for (int i = 1; i <= n; ++i)
        cin >> w[i];
    for (int i = 1; i <= n; ++i)
        cin >> b[i];
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cout << solve() << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, a, d;
    string s;
    (void)n;
    a = d = 0;
    cin >> n;
    cin >> s;
    for (auto c : s)
    {
        if (c == 'A')
            ++a;
        else
            ++d;
    }
    if (a == d)
        cout << "Friendship" << endl;
    else if (a > d)
        cout << "Anton" << endl;
    else
        cout << "Danik" << endl;
    return 0;
}

using namespace std;
int solve(int k, int r)
{
    int rem;
    for (int i = 1; i < 10; ++i)
    {
        rem = (i * k) % 10;
        if (rem == 0 or rem == r)
            return i;
    }
    return 10;
}
int main(void)
{
    int k, r;
    cin >> k >> r;
    cout << solve(k, r) << endl;
    return 0;
}

using namespace std;
inline int ord(char c) { return c - 'a'; }
int main(void)
{
    int ans = 0, last = 0;
    string s;
    cin >> s;
    for (auto c : s)
    {
        ans += min(26 - abs(ord(c) - last), abs(ord(c) - last));
        last = ord(c);
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int a[NMAX];
int main(void)
{
    int n, c, ans = 1;
    cin >> n >> c;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 1; i < n; ++i)
    {
        ++ans;
        if (a[i] - a[i - 1] > c)
            ans = 1;
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
const int CMAX = 2;
const int TMAX = 30;
struct node
{
    int cnt;
    node *children[CMAX];
    ~node()
    {
        cnt = 0;
        for (node *child : children)
            delete child;
    }
};
struct trie
{
    node *root;
    trie() { root = new node(); }
    void insert(int x)
    {
        node *cur = root;
        for (int i = TMAX; i >= 0; --i)
        {
            int j = (x >> i) & 1;
            if (cur->children[j] == nullptr)
                cur->children[j] = new node();
            cur = cur->children[j];
            cur->cnt += 1;
        }
    }
    void remove(int x)
    {
        node *cur = root;
        node *past;
        for (int i = TMAX; i >= 0; --i)
        {
            int j = (x >> i) & 1;
            past = cur;
            cur = cur->children[j];
            cur->cnt -= 1;
            if (cur->cnt == 0)
            {
                past->children[j] = nullptr;
                delete cur;
                return;
            }
        }
    }
    int query(int x)
    {
        int xi, yi, ans = 0;
        node *cur = root;
        for (int i = TMAX; i >= 0; --i)
        {
            xi = (x >> i) & 1;
            yi = 1 - xi;
            if (cur->children[yi] == nullptr)
                yi = xi;
            cur = cur->children[yi];
            ans ^= (xi ^ yi) << i;
        }
        return ans;
    }
};
int main(void)
{
    int q, x;
    char type;
    cin >> q;
    trie t;
    t.insert(0);
    while (q--)
    {
        cin >> type >> x;
        if (type == '+')
            t.insert(x);
        else if (type == '-')
            t.remove(x);
        else
            cout << t.query(x) << endl;
    }
    return 0;
}

using namespace std;
int n;
int a[100010];
int solve(void)
{
    int ans = 1;
    int cur = 1;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] > a[i - 1])
            ++cur;
        else
            cur = 1;
        ans = max(ans, cur);
    }
    return ans;
}
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << solve() << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
struct dsu
{
    int n;
    vi parent;
    vi sz;
    dsu(int n) : n(n)
    {
        parent.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
            sz[i] = 0;
        }
    }
    void merge_set(int u, int v)
    {
        u = find_set(u);
        v = find_set(v);
        if (u != v)
        {
            if (sz[u] < sz[v])
                swap(u, v);
            parent[v] = u;
            sz[u] += sz[v];
        }
    }
    int find_set(int u)
    {
        if (u == parent[u])
            return u;
        return parent[u] = find_set(parent[u]);
    }
};
int main(void)
{
    int n, m, u, v;
    vi p;
    cin >> n >> m;
    p.resize(n);
    dsu d(n);
    for (auto &pi : p)
        cin >> pi;
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v, u--, v--;
        d.merge_set(u, v);
    }
    vector<set<int, greater<int>>> sorted(n);
    for (int i = 0; i < n; ++i)
        sorted[d.find_set(i)].insert(p[i]);
    for (int i = 0; i < n; ++i)
    {
        int p = d.find_set(i);
        cout << *sorted[p].begin() << " ";
        sorted[p].erase(sorted[p].begin());
    }
    return 0;
}

using namespace std;
int main(void)
{
    int n, h, ai, ans = 0;
    cin >> n >> h;
    for (int i = 0; i < n; ++i)
    {
        cin >> ai;
        ans += 1 + (ai > h);
    }
    cout << ans;
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, ll>;
using vii = vector<ii>;
inline ll iceil(ll a, ll b) { return (a + b - 1) / b; }
int main(void)
{
    int n;
    vii a;
    cin >> n;
    a.resize(n);
    for (auto &[k, c] : a)
        cin >> k >> c;
    sort(a.begin(), a.end());
    for (int i = 1; i < n; ++i)
    {
        int dk = a[i].first - a[i - 1].first;
        if (dk < 15)
            a[i].second =
                max(a[i].second, iceil(a[i - 1].second, (1LL << (2 * dk))));
    }
    do
    {
        auto [k, c] = a.back();
        a.emplace_back(k + 1, iceil(c, (1LL << 2)));
    } while (a.back().second != 1);
    cout << a.back().first << endl;
    return 0;
}