# include using namespace std; typedef long long ll; const int M = 20; const int N = 10010; ll T, n; ll c[M], h[M]; ll dp[M][N]; int main() { scanf("%lld%lld", &T, &n); for (int i = 1; i <= n; i++) scanf("%lld", &c[i]); for (int i = 1; i <= n; i++) scanf("%lld", &h[i]); for (int i = 1; i <= n; i++) { for (int j = 0; j <= T; j++) { ll piou, fan; piou = h[i]; fan = 0; dp[i][j] = dp[i - 1][j]; for (int k = 1; k <= log2(h[i]) + 1; k++) { fan += piou; if (j >= k * c[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - k * c[i]] + fan); piou /= 2; } } } ll ans; ans = 0; for (int i = 0; i <= T; i++) ans = max(ans, dp[n][i]); printf("%lld\n", ans); return 0; }