#include #include #include #include #include #include #include #include using namespace std; #define FOR(i, s, e) for (int i = (s); i <= (e); i++) int N; int T; int c[20]; int v[20]; int dp[20][100010]; int dp_cou[20][10010]; vector Cs; vector Vs; int main() { FOR(i, 0, 19) FOR(j, 0, 10009) dp[i][j] = -1000000000; dp[0][0] = 0; cin >> T >> N; FOR(i, 0, N - 1) cin >> c[i]; FOR(i, 0, N - 1) { cin >> v[i]; while (v[i] > 0) { Vs.push_back(v[i]); Cs.push_back(c[i]); v[i] /= 2; } } int M = Cs.size(); FOR(i, 0, M - 1) { FOR(j, 0, T) { if(j - Cs[i] >= 0) { dp[i + 1][j] = max(dp[i][j] , dp[i][j - Cs[i]] + Vs[i]); } else { dp[i + 1][j] = dp[i][j]; } if(j > 0) dp[i + 1][j] = max(dp[i + 1][j],dp[i + 1][j - 1]); } } cout << dp[M][T] << endl; return 0; }