Problem Statement

Raymond has come to an amusement park to have fun.
He will stay at the amusement park for \(T\) hours, and the satisfaction of each attraction is as follows: riding the \(i\)-th attraction gives satisfaction \(V_i\).

However, every attraction at the amusement park has a queue, so it is hard to get on them.
For the queue of the \(i\)-th attraction, he can ride the attraction by waiting in line for \(c_i\) hours.
(The time of the attraction itself is included in the queue time.)

However, Raymond does not really want to ride the same attraction repeatedly.
If he rides the same attraction again during his stay, the satisfaction he gets is only "half of \(V_i\), with the fractional part truncated", and that value becomes the new \(V_i\).
After that, the satisfaction is halved each time he rides the same attraction again.

Suppose he wants to obtain the maximum satisfaction during the \(T\) hours of his stay. Find that satisfaction.

Input

\(T\)
\(N\)
\(c1 \, c2 \dots ci \dots cN\)
\(v1 \, v2 \dots vi \dots vN\)

The first line contains \(T (1 \le T \le 10000)\), representing the length of the stay.
The second line contains \(N (1 \le N \le 15)\), representing the number of attractions.
The third line contains \(ci (1 \le ci \le 100,1 \le i \le N)\), representing the queue time of each attraction.
The fourth line contains \(vi (1 \le vi \le 500,1 \le i \le N)\), representing the satisfaction of each attraction.

Output

Output the maximum satisfaction Raymond can obtain.
Print a newline at the end.

Sample

5
3
1 2 3
3 2 1

6

9
2
8 2
9 7

11

9
2
8 2
9 5

9

20
5
10 7 9 5 7
5 8 2 8 1

20