P1230 Intellectual Surfing

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.

- 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 a single line: the maximum amount of money Xiaowei can win.

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