Chúng ta sẽ tìm kiếm nhị phân trên số lượng quái vật có thể đánh bại.Nói cách khác,chúng ta sẽ tìm kiếm trên khoảng ~[0, min(size(a),size(b))]~.

Bây giờ chúng ta sẽ đi xây dựng logic check cho tìm kiếm nhị phân.Với mỗi lần chặt chúng ta cần kiểm tra xem có thể đánh bại được mid quái vật hay không. Lúc này là lúc chúng ta sử dụng tham lam, chọn những quái vật yêu cầu sức mạnh nhỏ nhất cần để đánh bại một cách hợp lý.

Đầu tiên,mỗi con quái có thể rơi vào ba trường hợp:

1. Một anh hùng không cần nâng sức mạnh vẫn có thể đánh bại được.

2. Một anh hùng cần nâng sức mạnh mới có thể đánh bại được.

3. Không có anh hùng nào có thể đánh bại, dù có được nâng sức mạnh hay không.

Vì có giới hạn số lượng tiền vàng, nên chúng ta ưu tiên trường hợp đầu tiên. Nếu không thể, chuyển sang trường hợp thứ hai. Nếu cả hai trường hợp này đều không thể và rơi vào trường hợp thứ ba, thì chắc chắn rằng không thể hoàn thành được mid số nhiệm vụ.

Đối với trường hợp đầu tiên, chúng ta có thể chọn anh hùng mạnh nhất có sẵn. Nhưng đối với trường hợp thứ hai (khi cần nâng sức mạnh), tốt hơn là chọn anh hùng yếu nhất có thể đánh bại được con quái khi được nâng sức mạnh. Việc gán con quái cho anh hùng mạnh hơn khi có anh hùng yếu hơn vẫn có thể sử dụng để đánh bại con quái có thể dẫn đến tình huống sau này khi đánh bại con quái này, anh hùng yếu không thể đánh bại các con quái sau nhưng anh hùng mạnh có thể thì lại đi đánh quái trước rồi.

Nếu gặp trường hợp thứ ba hoặc số lượng đồng vàng cần thiết để đánh mid quái vượt quá giới hạn, chúng ta cần tìm kiếm ở giá trị nhỏ hơn của mid. Ngược lại, nếu không gặp vấn đề gì, chúng ta kiểm tra giá trị lớn hơn của mid.

Cài đặt:

Ở đây ta có thể sử dụng multiset để lưu trữ các anh hùng trong mỗi lần chặt. Điều này giúp sử dụng các hàm STL hữu ích và rõ ràng. multiset giữ các phần tử theo thứ tự tăng dần theo mặc định.

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define el cout << "\n"
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define f0(i, n) for(int i = 0; i < n; i++)
#define f1(i, n) for(int i = 1; i <= n; i++)
#define pll pair<ll, pair<ll, ll>>
#define faster ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define file(name) if(fopen(name".inp", "r")) { freopen(name".INP", "r", stdin); freopen(name".OUT", "w", stdout); }
const int MAXN = 1e6 + 5;
const int mod = 1e9 + 7;

int32_t main() {
    faster;
    file();
    int n, m, k, x;
    cin >> n >> m >> k >> x;
    vector<int> a(n);
    vector<int> b(m);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;
    sort(all(a));
    sort(all(b));
    int l = 0, r = min(m, n);
    int ans;
    while (l <= r) {
        int mid = l+r>>1;
        int cnt = 0;
        bool ok = true;
        // Chèn tất cả các anh hùng vào một multiset
        multiset<int> ms(b.begin(), b.end());

        // Kiểm tra xem có thể gán mid con quái nhỏ nhất không
        for (int i = mid - 1; i >= 0; i--) {

            // Trường hợp 1: Cố gắng gán cho một anh hùng mà không cần tăng sức mạnh
            auto it = prev(ms.end());
            if (a[i] <= *it) {

                // Trường hợp 1 đạt yêu cầu!
                ms.erase(it);
            } else {

                // Trường hợp 2: Cố gắng gán cho một anh hùng cần tăng sức mạnh
                auto it = ms.lower_bound(a[i] - x);
                if (it != ms.end()) {

                    // Trường hợp 2 đạt yêu cầu!
                    cnt++;
                    ms.erase(it);
                } else {

                    // Trường hợp 3: Không thể gán mid con quái
                    ok = false;
                    break;
                }
            }

            // Nếu tại bất kỳ thời điểm nào, số lượng tiền cần thiết để gán mid con quái vượt quá số lượng đồng tiền được phép,
            // dừng vòng lặp
            if (cnt > k) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
}