\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Thử từng dãy có thể và với mỗi dãy duyệt theo thứ tự, nếu dãy đó thỏa mãn thì cập nhật vô kết quả

\(\color{orange}{\text{Hint 2 <Greedy>}}\)

• Duyệt qua mảng, nếu cặp \((a_i, b_i)\) nào mà \(a_i \leq k\) thì thêm \(b_i\) vào \(k\), tăng biến đếm, xóa phần tử đó và duyệt tới khi không còn phần tử nào thỏa

\(\color{orange}{\text{Hint 3 <Sorting> <Greedy>}}\)

• Sắp xếp mảng tăng dần theo \(a_i\), và cứ mỗi \(a_i\) bé hơn \(k\) mình sẽ thêm \(b_i\) vào \(k\), tăng biến đếm

\(\color{green}{\text{Preference AC Code }}\): Sorting, Greedy

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll n, k;
    cin >> n >> k;

    vector<pair<int, int> > a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].first >> a[i].second;

    int cnt = 0;
    sort(all(a));
    for (int i = 0; i < n; ++i)
    {
        if (k < a[i].first) break;
        else
        {
            k += a[i].second;
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

\(\color{orange}{\text{Hint 4 <STL> <Online Solving> <Greedy>}}\)

• Gọi \(M[a] = sum(b)\) là giá trị của tổng các \(b_i\) của các cặp có \(a = a_i\) đang xét

• Gọi \(F[a] = count(b)\) là số lượng các \(b_i\) của các cặp có \(a = a_i\) đang xét

• Gọi \((a, b)\) là cặp hiện tại đang xét

• Nếu \(k > a\) thì ta thêm \(b\) vào \(M[a]\) và tăng \(F[a]\) lên 1

• Nếu \(k \leq a\) thì ta thêm \(b\) vào \(k\)

Trong khi các phần tử \(v = min(a) \in M\) mà \(v \leq k\)

Ta thêm \(M[a]\) vào \(k\) và tăng biến đếm lên \(F[a]\)

Sau đó ta xóa \(a\) ra khỏi \(M[]\) và \(F[]\)

\(\color{green}{\text{Preference AC Code }}\): STL, Online Solving, Greedy

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

int main()
{
    ll n, k;
    cin >> n >> k;

    int cnt = 0;
    map<int, int> M;
    map<int, int> F;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;

        if (a <= k)
        {
            for (k += b, cnt++; !M.empty(); )
            {
                int v = M.begin() -> first;
                if (v <= k)
                {
                    k   += M[v];
                    cnt += F[v];
                    M.erase(v);
                    F.erase(v);
                }
                else break;
            }
        }
        else
        {
            M[a] += b;
            F[a]++;
        }
    }
    cout << cnt;
    return 0;
}