Description

Xiaowei signed up for China Central Television (CCTV)'s “Intellectual Surfing” show. This challenge has attracted many contestants. To honor everyone’s courage, the host first awards each contestant $m$ yuan. Don’t celebrate too soon, because this money may not all be yours. Next, the host announces the rules:

First, the contest time is divided into $n$ time slots, and the host also provides many mini-games. Each mini-game must be completed before its deadline $t_i$. If a game is not completed before its deadline, a penalty $w_i$ will be deducted from the $m$ yuan award. Here $w_i$ are natural numbers, and the deduction differs from game to game. Of course, every game itself is very simple: each contestant can finish any single game within one time slot, and each game must start at the beginning of a whole time slot. The host only wants to test how each contestant schedules the order of games. As a contestant, Xiaowei wants to win the championship and, of course, the most money! Note: The contest will never make contestants lose money.

Input Format

• The first line contains $m$, the initial award for each contestant.
• The second line contains $n$, the number of mini-games.
• The third line contains $n$ numbers, the deadlines of games $1$ through $n$.
• The fourth line contains $n$ numbers, the penalty amounts if games $1$ through $n$ are not completed before their deadlines.

Output Format

Output a single line: the maximum amount of money Xiaowei can win.

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

9950

Hint

Constraints: For $100\%$ of the testdata, $1 \le n \le 500$, $1 \le m \le 5 \times 10^5$, $1 \le t_i \le n$, $1 \le w_i \le 1000$.

Translated by ChatGPT 5