While practising problems from hackerearth I came across following problem( not from active contest ) and have been unsuccessful in solving it after many attempts.

> 
> Chandler is participating in a race competition involving N track
>  races. He wants to run his old car on these tracks having F amount of
>  initial fuel. At the end of each race, Chandler spends si fuel and
>  gains some money using which he adds ei amount of fuel to his car.
> 
> 
> Also for participating in race i at any stage, Chandler should have
>  more than si amount of fuel. Also he can participate in race i once.
>  Help Chandler in maximizing the number of races he can take part in if
>  he has a choice to participate in the given races in any order.
> 
> 
> 

How can I approach the problem. My approach was to sort by `(ei-si)` but than I couldn't incorporate condition that fuel present is greater than required for race.

**EDIT** I tried to solve using following algorithm but it fails,I also can't think of any inputs which fail the algorithm. Please help me out figuring whats wrong or give some input where my algorithm fails.

```
Sort (ei-si) in non-increasing order;
start iterating through sorted (ei-si) and find first element such that fuel>=si
   update fuel=fuel+(ei-si);
   update count;
   erase that element from list, and start searching again;

if fuel was not updated than we can't take part in any races so stop searching 
and output count.

```

**EDIT** And here is my code as requested.

```
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>

using namespace std;
struct race{
    int ei;
    int si;
    int earn;

};

bool compareByEarn(const race &a, const race &b)
{
    return a.earn <= b.earn;
}

int main(){

    int t;
    cin>>t;
    while(t--){
        vector<struct race> fuel;
        int f,n;
        cin>>f>>n;
        int si,ei;
        while(n--){
            cin>>si>>ei;
            fuel.push_back({ei,si,ei-si});

        }
        sort(fuel.begin(),fuel.end(),compareByEarn);
        list<struct race> temp;
        std::copy( fuel.rbegin(), fuel.rend(), std::back_inserter(temp ) );

        int count=0;
        while(1){

            int flag=0;
            for (list<struct race>::iterator ci = temp.begin(); ci != temp.end(); ++ci){
                if(ci->si<=f){
                    f+=ci->earn;
                    ci=temp.erase(ci);
                    ++count;
                    flag=1;
                    break;

                }
            }

            if(!flag){
                break;
            }
        }

        cout<<count<<endl;

    }

}

```

**EDIT** As noted in answer below, the above greedy approach dosen't always work. So now any alternative method would be useful