You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

逛游乐园

题目描述

辰辰 正在游乐园玩，游乐园一共有 $n$ 个场地，每个场地都可以玩很多次，玩一次第 $i$ 个场地需要 $c_i$ 分钟，获得 $a_i$ 点快乐值。由于玩多了一个场地就会丧失趣味，所以辰辰 每多玩一次，所获得的快乐值就会减半（向下取整）。

现在辰辰 想知道，如果他最多只能在游乐园待 $t$ 分钟，那么他最多能获得多少快乐值。

输入格式

第一行两个整数 $t,n$。

接下来两行，每行 $n$ 个整数，第一行代表数组 $c$，第二行代表数组 $a$。

输出格式

一行一个整数，表示答案。

5 3
1 2 3
3 2 1

6

样例解释 1

辰辰 先玩一次 $1$ 场地，然后玩两次 $2$ 场地，获得的快乐值为 $3+2+1=6$，可以证明，这是最大的方案。

数据范围与约定

对于 $10\%$ 的数据，$n=1$。

对于另外 $20\%$ 的数据，$h_i=1$。

对于 $100\%$ 的数据，$1\le n\le 15,1\le t\le 10^4,1\le c_i,h_i\le 500$。