/*
* 037_sample.cpp
* 
* No.37 遊園地のアトラクション
* 難易度3
*/

#include <iostream>
#include <vector>
#include <cstdio>

using VEC = std::vector<int>;


int main () {
	// 標準入力
	int T = 0;		// 滞在時間
	int N = 0;		// アトラクションの数
	std::cin >> T >> N;
	VEC c(N*9+1);		// アトラクションの待ち時間(+乗り物の時間)
	VEC v(N*9+1);		// 満足度
	for (int i = 0; i < N; i++) {
		std::cin >> c[i];
	}
	for (int i = 0; i < N; i++) {
		std::cin >> v[i];
	}

	// 初期化
	int dp[N+1][T+1];
	for (int i = 0; i < N+1; i++) {
		for (int j = 0; j < T+1; j++) {
			dp[i][j] = -1;
		}
	}

	// dp[アトラクション数][待ち時間の合計]=満足度
	// 0番目かつ時間0は1つもアトラクションに乗っていない状態の為満足度0
	dp[0][0] = 0;
	
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j <= T; ++j) {
			int sum = 0;
			dp[i+1][j] = dp[i][j];
			for (int k = v[i], count = 1; 0 <= k; k /= 2, count++ ) {
				// 繰り返し同じアトラクションに乗るたび満足度が減少
				// 0となるとそれ以上は乗っても意味がない為打ち切り
				if (k == 0) {
					break;
				}
				// i番目の満足度合計
				sum += k;
				if (j - c[i] * count >= 0) {
					// i番目のアトラクションにcount回数乗ったときの合計時間が
					// 滞在時間を超えていない場合
					if (dp[i][j - c[i] * count] != -1) {
						dp[i+1][j] = std::max(dp[i+1][j], dp[i][j - c[i] * count] + sum);
					}
				}
			}
		}
	}
	
	// 最終的に最後の街でかかった時間で一番小さいものを答えとする
	int ans = 0;
	for (int i = 0; i <= T; ++i) {
		ans = std::max(ans, dp[N][i]);
	}
	
	// 最後の街までたどり着けていない場合は-1とする
	std::cout << ans << std::endl;

	return 0;
	
}