Description

Xiao Wei signed up for a quiz show on CCTV. This challenge attracted many participants, and to commend everyone's courage, the host first rewarded each contestant with $m$ yuan. Don't get too happy yet! Because this money isn't necessarily all yours?! The host then announced the rules of the competition:

First, the competition time is divided into $n$ periods. The host also provided many mini-games, each of which must be completed before its specified deadline $t_i$. If a game is not completed before the deadline, a portion of the reward money $m$ yuan will be deducted, with $w_i$ being a natural number, and the amount deducted varies for different games. Of course, each game itself is very simple, ensuring that every contestant can complete it within one period and must start at the beginning of a period. The host just wants to test how each contestant arranges the order of playing the games. As a contestant, Xiao Wei is eager to win the championship and, of course, to earn the most money! Note: The competition will absolutely not leave contestants losing money!

Input Format

The input consists of four lines.

The first line is $m$, representing the initial amount of money rewarded to each contestant;

The second line is $n$, indicating there are $n$ mini-games;

The third line contains $n$ numbers, representing the deadlines for games $1$ to $n$;

The fourth line contains $n$ numbers, representing the penalty amounts for games $1$ to $n$ if not completed before the deadline.

Output Format

The output consists of a single line, indicating the maximum amount of money Xiao Wei can win.

Sample 1

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

9950

Data Range and Hint

For $100\%$ of the data, $n\le 500$, and $1\le t_i\le n$.