def main():
    import sys

    T = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    c_list = list(map(int, sys.stdin.readline().split()))
    v_list = list(map(int, sys.stdin.readline().split()))

    # Preprocess each attraction to generate viable (time, value) options
    groups = []
    for ci, vi in zip(c_list, v_list):
        options = []
        sum_t = 0
        sum_v = 0
        current_v = vi
        while True:
            sum_t += ci
            sum_v += current_v
            # Break if sum_t exceeds T
            if sum_t > T:
                break
            options.append((sum_t, sum_v))
            current_v = current_v // 2
            if current_v == 0:
                break
        # Filter to keep only time-efficient and value-increasing options
        filtered = []
        max_value = -1
        for t, v in options:
            if v > max_value:
                filtered.append((t, v))
                max_value = v
        groups.append(filtered)

    # Initialize DP array
    dp = [0] * (T + 1)

    # Process each group with group knapsack approach
    for group in groups:
        prev_dp = dp.copy()
        for t, v in group:
            for j in range(T, t - 1, -1):
                if prev_dp[j - t] + v > dp[j]:
                    dp[j] = prev_dp[j - t] + v

    # Find the maximum value within the time limit
    print(max(dp[:T+1]))

if __name__ == '__main__':
    main()