Hướng dẫn:

Nhận xét: Con đường hái hoa tối ưu nhất của Marisa là hái những bông hoa ở những vị trí theo thứ tự tăng dần, có nghĩa là nếu Marisa hái bông hoa ở vị trí x thì bông hoa tiếp theo Marisa có thể hái phải là y với y > x.

Giả sử: Marisa hái bông hoa ở vị trí x

• Nếu Marisa hái bông hoa y (y < x) thì phải mất thêm chi phí đi từ x về y cộng với thời gian hái hoa ở y.
• Trong khi đó Marisa bắt đầu từ vị trí 0 đi đến x thì trên đường đi Marisa có thể dừng lại hái hoa ở y xong rồi mới đi đến hái hoa ở x.

Rõ ràng Marisa hái hoa ở vị trí x rồi hái hoa ở vị trí y (y > x) là phương pháp tối ưu nhất.

Code:

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b)  for (int i=a; i<=b; ++i)

template<class X, class Y> 
    bool maximize(X &x, const Y &y){return (x < y) ? x = y, 1 : 0;}

#define ii pair<int,int>
const int MAXN = 1e6 + 5;
priority_queue<int> pq;
int n,m;
ii a[MAXN];

signed main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    FOR(i,1,n) cin >> a[i].first >> a[i].second;
    sort(a+1,a+n+1);

    int res = 0;
    int cur = 0;
    FOR(i,1,n)
    {
        pq.push(a[i].second);
        cur += a[i].second;
        while (pq.size() && cur + a[i].first > m)
        {
            cur -= pq.top();
            pq.pop();
        }
        maximize(res,pq.size());
    }
    cout << res;

    return 0;
}