#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class AlbertoTheAviator { public:
int MaximumFlights(int F, vector <int> duration, vector <int> refuel)
{
const int N = duration.size();
vector<pair<int,int>> mp;
for(int i=0; i<N; ++i)
mp.emplace_back(duration[i], refuel[i]);
// Larger refuel first.
sort(mp.begin(), mp.end(), [&](const pair<int,int>& lhs, const pair<int,int>& rhs){
if(lhs.second != rhs.second)
return lhs.second > rhs.second;
return lhs.first < rhs.first;
});
const int BAD = -0x3fffffff;
vector<int> dp(F+1, BAD);
dp[F] = 0;
for(auto& mpi: mp) {
int minus = mpi.first;
int plus = mpi.second;
vector<int> dp2 = dp;
for(int f=minus; f<=F; ++f)
dp2[f-minus+plus] = max(dp2[f-minus+plus], dp[f]+1);
dp.swap(dp2);
}
return *max_element(dp.begin(), dp.end());
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, AlbertoTheAviator().MaximumFlights(F, duration, refuel));}
int main(){
CASE(0)
int F = 10;
int duration_[] = {10};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {0};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 1;
END
CASE(1)
int F = 10;
int duration_[] = {8, 4};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {0, 2};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 2;
END
CASE(2)
int F = 12;
int duration_[] = {4, 8, 2, 1};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {2, 0, 0, 0};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 3;
END
CASE(3)
int F = 9;
int duration_[] = {4, 6};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {0, 1};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 2;
END
CASE(4)
int F = 100;
int duration_[] = {101};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {100};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 0;
END
CASE(5)
int F = 1947;
int duration_[] = {2407, 2979, 1269, 2401, 3227, 2230, 3991, 2133, 3338, 356, 2535, 3859, 3267, 365};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {2406, 793, 905, 2400, 1789, 2229, 1378, 2132, 1815, 355, 72, 3858, 3266, 364};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = 3;
END
CASE(6)
int F = 5000;
int duration_[] = {948,914,915,945,952,939,925,951,957,978,926,973,986,949,992,932,968,916,946,901,929,956,976,941,938,980,984,906,979,907,923,931,963,964,932,910,909,981,969,997,936,930,956,949,903,914,954,945,913,969};
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = {819,852,834,789,875,833,760,887,796,831,900,805,758,794,882,855,709,803,793,704,760,802,714,881,890,881,839,754,844,896,806,713,809,738,763,749,768,818,732,706,830,702,741,769,816,742,791,803,761,865};
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = -1;
END
/*
CASE(7)
int F = ;
int duration_[] = ;
vector <int> duration(duration_, duration_+sizeof(duration_)/sizeof(*duration_));
int refuel_[] = ;
vector <int> refuel(refuel_, refuel_+sizeof(refuel_)/sizeof(*refuel_));
int _ = ;
END
*/
}
// END CUT1 HERE900