题目链接 ：https://www.luogu.org/problemnew/show/P1417
直接背包 -> 30'
考虑直接背包的问题：在DP时第i种食材比第j种食材更优，但由于j<i导致第j种食材先被决策到，故 GG
显然：当i，j满足 f[t]+a[i]-b[i]*(c[i]+t) > f[t]+a[j]-b[j]*(c[j]+t) <=> b[i]*c[i] < b[j]*c[j] 第i种更优；
//Author : 15owzLy1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define lson tl, mid, rt<<1
#define rson mid+1, tr, rt<<1|1
#define pb(__) push_back(__)
#define fr() front()
#define bg() begin()
#define it iterator
#define INF 2100000000
typedef long long ll;
typedef double db;
template<class T>inline void get_max(T &_, T __) { _=_>__?_:__; }
template<class T>inline void get_min(T &_, T __) { _=_<__?_:__; }
template<class T>inline void Swap(T &_, T &__) { T ___=_;_=__;__=___; }
template<class T>inline T abs(T _) { return _>?_:-_; }
template<typename T>inline void read(T &_) {
_=;bool __=;char ___=getchar();
while(___<''||___>''){__|=(___=='-');___=getchar();}
while(___>=''&&___<=''){_=(_<<)+(_<<)+(___^);___=getchar();}
_=__?-_:_;
} const int N = , M = ;
struct node {
int a, b, c;
bool operator < (const node x) const {
return 1ll*this->c*x.b < 1ll*this->b*x.c;
}
}dish[N];
int T, n;
ll res, f[M]; int main() {
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
read(T), read(n);
for(int i=;i<=n;i++) read(dish[i].a);
for(int j=;j<=n;j++) read(dish[j].b);
for(int k=;k<=n;k++) read(dish[k].c);
std::sort(dish+, dish++n);
for(int i=;i<=n;i++)
for(int j=T;j>=dish[i].c;j--) {
get_max(f[j], f[j-dish[i].c]+1ll*dish[i].a-1ll*j*dish[i].b);
get_max(res, f[j]);
}
printf("%lld\n", res);
fclose(stdin);
fclose(stdout);
return ;
}