Sorting in 2 quantities Problem

help
,
1

You have N cup noodles. Each takes ci time to cook and satisfies hi hunger. You can cook a cup noodle by pouring hot water, you can only pour hot water in a noodle cup in one minute. You have M minutes, find the maximum possible hunger satisfaction.

constraints :
1 <= N <= 10^5
1 <= M <= 10^5
1 <= ci <= 10^5
1 <= hi <= 10^5

testcases -
n = 3 m = 5
c → 2 5 5
h → 10 5 10
Output - 20
explaination - We cook the third cup first and then the second cup to get maximum satisfaction of 20.

n = 3 m = 5
c → 5 5 3
h → 5 10 2
Output - 12
exp - Cook the second cup first and second one in the next minute. Both will be done by 5 minutes.
My thought process -
Afaik, the constraints rule out a DP approach to this problem. So this problem probably boils down to some sorting and greedy algorithm.

so I sort by hunger satisfaction and greedily try to cook noodles with large times first with maximum satisfaction.

#include<bits/stdc++.h>
using namespace std;

bool comp(pair<int,int>& a, pair<int,int>& b) {
    if(a.second == b.second) return a.first > b.first;
    return a.second > b.second;
}

int solve (int n, int m, vector<int> c, vector<int> h) {
   // Write your code here
   vector<pair<int,int>> a(n);

   for(int i = 0; i < n; i++) {
       a[i].first = c[i];
       a[i].second = h[i];
    }

    sort(a.begin(), a.end(), comp);

    int ans = 0, taken = 0;
    for(int i = 0; i < n; i++) {
        if(a[i].first <= m - taken) {
            ans += a[i].second;
            taken++;
        }
    }
    return ans;
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i = 0; t_i < T; t_i++)
    {
        int N;
        cin >> N;
        int M;
        cin >> M;
        vector<int> c(N);
        for(int i_c = 0; i_c < N; i_c++)
        {
        	cin >> c[i_c];
        }
        vector<int> h(N);
        for(int i_h = 0; i_h < N; i_h++)
        {
        	cin >> h[i_h];
        }

        int out_;
        out_ = solve(N, M, c, h);
        cout << out_;
        cout << "\n";
    }
}

I could pass 7/10 testcases in the problem. Any solutions to this problem will be greatly appreciated, thanks in advance.

P.S. If anyone can point out a few similar problems, would be great.

2

a similar problem recently came in codeforces. if you observe , say a noodle takes takes t minutes ( t <= M ) then you must cook the noodle atleast t minutes before the M minutes ends. if a noodle takes t minutes then you must cook it before or at (M - t + 1)th minute. say there are multiple noodles with time t. then you can choose at max. (M-t+1) of them. { cuz you can use them at 1st , 2nd … (M-t+1)th minute.} . so first discard all t > M. now for all t <= M , for each t , choose first (M-t+1) largest happiness noodles. now use all of these noodles for each t. and at the end discard some of them such that number of noodles = m.