using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<ll>;
ll n, T, a, b;
vector<ii> time_cost;
ll get_extra(ll window, ll easy_left, ll hard_left)
{
    auto temp_extra = min(window / a, easy_left), extra = temp_extra;
    window -= a * temp_extra;
    temp_extra = min(window / b, hard_left), extra += temp_extra;
    window -= b * temp_extra;
    return extra;
}
int solve(void)
{
    ll ans(0), acc_cost(0), taken_prev = 0;
    ll easy_left =
        count_if(time_cost.begin(), time_cost.end(), [](ii tc) { return tc.second == a; });
    ll hard_left =
        count_if(time_cost.begin(), time_cost.end(), [](ii tc) { return tc.second == b; });
    sort(time_cost.begin(), time_cost.end());
    time_cost.emplace_back(T + 1, a);
    for (auto [t, c] : time_cost)
    {
        ll new_acc_cost = acc_cost + c, cur = 0;
        taken_prev = n - (easy_left + hard_left);
        if (acc_cost < t)
            cur = max(cur,
                      taken_prev + get_extra(max((t - 1) - acc_cost, 0LL),
                                             easy_left,
                                             hard_left));
        if (c == a)
            easy_left--;
        else
            hard_left--;
        acc_cost = new_acc_cost;
        ans = max(ans, cur);
    }
    return ans;
}
int main(void)
{
    int tc;
    cin >> tc;
    while (tc--)
    {
        cin >> n >> T >> a >> b;
        time_cost.resize(n);
        for (auto &[t, c] : time_cost)
            cin >> c, c = (c ? b : a);
        for (auto &[t, c] : time_cost)
            cin >> t;
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 2e5 + 11;
int n, p, k, a[NMAX], dp[NMAX];
int solve(void)
{
    int ans = 0;
    dp[0] = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = a[i];
        if (i - k >= 0)
            dp[i] += dp[i - k];
        else
            dp[i] += dp[i - 1];
    }
    for (int i = 1; i <= n; ++i)
    {
        if (dp[i] <= p)
            ans = max(ans, i);
    }
    return ans;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> p >> k;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
int const MOD = 1e9 + 7;
inline int add(ll a, ll b) { return ((a % MOD) + (b % MOD)) % MOD; }
inline int mult(ll a, ll b) { return ((a % MOD) * (b % MOD)) % MOD; }
int solve(int x, string s)
{
    int n = s.size();
    for (int i = 1; i <= x; ++i)
    {
        int rep = s[i - 1] - '1';
        n = add(n, mult(n - i + MOD, rep));
        if ((int)s.size() <= x)
        {
            string sright(s.begin() + i, s.end());
            while (rep--)
                s += sright;
        }
    }
    return n;
}
int main(void)
{
    int t, x;
    string s;
    cin >> t;
    while (t--)
    {
        cin >> x >> s;
        cout << solve(x, s) << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
vi g[NMAX], gi[NMAX], odds, evens;
int n, a[NMAX], visited[NMAX], dp[NMAX];
vi msbfs(vi srcs)
{
    vector<int> visited(n + 1, false);
    queue<int> frontier;
    vector<int> dist(n + 1, -1);
    for (auto x : srcs)
    {
        dist[x] = 0;
        frontier.push(x);
        visited[x] = true;
    }
    while (not frontier.empty())
    {
        auto u = frontier.front();
        frontier.pop();
        for (auto v : gi[u])
        {
            if (not visited[v])
            {
                frontier.push(v);
                visited[v] = true;
                dist[v] = dist[u] + 1;
            }
        }
    }
    return dist;
}
int main(void)
{
    cin >> n;
    for (int u = 1; u <= n; ++u)
        cin >> a[u];
    for (int u = 1; u <= n; ++u)
    {
        int l = u - a[u], r = u + a[u];
        if (l >= 1)
            g[u].push_back(l), gi[l].push_back(u);
        if (r <= n)
            g[u].push_back(r), gi[r].push_back(u);
        a[u] &= 1LL;
        if (a[u])
            odds.push_back(u);
        else
            evens.push_back(u);
    }
    vi ans(n + 1);
    auto d1 = msbfs(odds);
    for (int u = 1; u <= n; ++u)
        if (d1[u] != 0)
            ans[u] = d1[u];
    auto d2 = msbfs(evens);
    for (int u = 1; u <= n; ++u)
        if (d2[u] != 0)
            ans[u] = d2[u];
    for (int u = 1; u <= n; ++u)
        cout << ans[u] << " ";
    cout << endl;
    return 0;
}

using namespace std;
int main(void) {
  int a, b, c, d, e, f, ne, nf;
  cin >> a >> b >> c >> d >> e >> f;
  auto ex = [&]() {
    ne = min(a, d);
    d -= ne;
  };
  auto fx = [&]() {
    nf = min({b, c, d});
    d -= nf;
  };
  if (e >= f) {
    ex();
    fx();
  } else {
    fx();
    ex();
  }
  cout << e * ne + f * nf << endl;
  return 0;
}

using namespace std;
using ll = long long;
int main(void)
{
    ll t, x1, y1, x2, y2;
    cin >> t;
    while (t--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (x2 - x1) * (y2 - y1) + 1 << endl;
    }
    return 0;
}

using namespace std;
const int NMAX = 1e5 + 11;
int n, a[NMAX];
int solve(void)
{
    int grannies = 0;
    bool found = false;
    sort(a, a + n);
    for (int i = n - 1; i >= 0; --i)
    {
        grannies = i + 1;
        if (grannies >= a[i])
        {
            found = true;
            break;
        }
    }
    return grannies + found;
}
int main(void)
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        cout << solve() << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 2e5 + 11;
int n, m;
vi g[NMAX];
set<int> edges;
int dfs(int u, vector<bool> &visited)
{
    int maxv = u;
    visited[u] = true;
    for (auto v : g[u])
        if (not visited[v])
            maxv = max(maxv, dfs(v, visited));
    return maxv;
}
int solve(void)
{
    int ans = 0;
    vector<bool> visited(n + 1, false);
    while (not edges.empty())
    {
        int u = *edges.begin(), v = dfs(u, visited);
        for (int i = u; i <= v; ++i)
        {
            if (not visited[i])
            {
                g[u].push_back(i);
                g[i].push_back(u);
                v = max(v, dfs(i, visited));
                ++ans;
            }
            edges.erase(i);
        }
    }
    return ans;
}
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        edges.insert(u), edges.insert(v);
    }
    cout << solve() << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
struct fenwick
{
    int n;
    vi bit;
    fenwick() {}
    fenwick(int n_) : n(n_ + 1) { bit.assign(n_ + 1, 0); }
    void update(int i, int delta)
    {
        while (i < n)
        {
            bit[i] += delta;
            i += (i & -i);
        }
    }
    int prefix_sum(int r) const
    {
        int ans = 0;
        while (r > 0)
        {
            ans += bit[r];
            r -= (r & -r);
        }
        return ans;
    }
    int sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l - 1); }
};
fenwick zcnt, ncnt;
vi a;
void change(int i, int v)
{
    if ((a[i] == 0 and v == 0) or (a[i] < 0 and v < 0))
        return;
    if (a[i] == 0)
    {
        zcnt.update(i, -1);
        if (v < 0)
            ncnt.update(i, +1);
    }
    else if (a[i] < 0)
    {
        ncnt.update(i, -1);
        if (v == 0)
            zcnt.update(i, +1);
    }
    else
    {
        if (v == 0)
            zcnt.update(i, +1);
        else if (v < 0)
            ncnt.update(i, +1);
    }
}
char product(int l, int r)
{
    int zeros = zcnt.sum(l, r);
    if (zeros > 0)
        return '0';
    int neg = ncnt.sum(l, r);
    if (neg % 2 == 0)
        return '+';
    else
        return '-';
}
int main(void)
{
    int n, k, l, r, j, x;
    char type;
    while (cin >> n >> k)
    {
        a = vi(n + 1);
        zcnt = fenwick(n);
        ncnt = fenwick(n);
        for (int i = 1; i <= n; ++i)
        {
            cin >> a[i];
            if (a[i] == 0)
                zcnt.update(i, 1);
            else if (a[i] < 0)
                ncnt.update(i, 1);
        }
        while (k--)
        {
            cin >> type;
            if (type == 'C')
            {
                cin >> j >> x;
                change(j, x);
                a[j] = x;
            }
            else
            {
                cin >> l >> r;
                cout << product(l, r);
            }
        }
        cout << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
using vi = vector<int>;
int const NMAX = 1e5;
ll const INF = 1e17;
int n, c[3][NMAX];
vi g[NMAX];
int main(void)
{
    int u, v;
    cin >> n;
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < n; ++j)
            cin >> c[i][j];
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v, u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    try
    {
        int leaf = distance(
            g, find_if(g, g + n, [](vi const &adj) { return (int)adj.size() == 1; }));
        vi a(n), p = {0, 1, 2};
        int prv = -1, u = leaf;
        for (int i = 0; i < n; ++i)
        {
            a[i] = u;
            if (prv != -1)
                g[u].erase(find(g[u].begin(), g[u].end(), prv));
            if ((int)g[u].size() > 1)
                throw -1;
            if (i < n - 1)
            {
                prv = u;
                u = g[u].back();
            }
        }
        vector<vi> ps(6);
        int k;
        ll ans = INF;
        for (int i = 0; i < 6; ++i, next_permutation(p.begin(), p.end()))
        {
            ps[i] = p;
            ll cur = 0;
            for (int j = 0; j < n; ++j)
                cur += c[p[j % 3]][a[j]];
            if (cur < ans)
            {
                ans = cur;
                k = i;
            }
        }
        vi ansv(n);
        for (int i = 0; i < n; ++i)
            ansv[a[i]] = ps[k][i % 3] + 1;
        cout << ans << endl;
        for (int i = 0; i < n; ++i)
            cout << ansv[i] << " ";
        cout << endl;
    }
    catch (int e)
    {
        cout << e << endl;
    }
    return 0;
}