#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } int main() { int T; while(~scanf("%d", &T)) { int N; scanf("%d", &N); vector c(N); for(int i = 0; i < N; ++ i) scanf("%d", &c[i]); vector v(N); for(int i = 0; i < N; ++ i) scanf("%d", &v[i]); vector dp(T+1); for(int i = 0; i < N; ++ i) { int w = v[i]; while(w > 0) { for(int j = T - c[i]; j >= 0; -- j) amax(dp[j + c[i]], dp[j] + w); w /= 2; } } int ans = *max_element(dp.begin(), dp.end()); printf("%d\n", ans); } return 0; }