Description

Xiao Wei signed up for an OJ competition show. This challenge attracted many OIers. To commend everyone's courage, the host first rewarded each contestant with m yuan (m < max). However, this money isn't necessarily all yours yet. The host then announced the competition rules:

First, the competition time is divided into n periods (n ≤ 500). The host provided many beginner-level problems like A+B Problem. Each problem must be completed before its specified deadline ti (1 ≤ ti ≤ n). If a problem is not completed before its deadline, a portion of the reward money, wi, will be deducted from the m yuan. Here, wi is a natural number, and the deduction amounts vary for different problems. Of course, each problem itself is very simple, ensuring that every contestant can complete it within one period, and all problems must start at the beginning of a full period. The host simply wants to test how each contestant arranges the order of solving the problems. As an outstanding OIer, Xiao Wei is eager to win the championship and, more importantly, to earn the most money!

Note: The competition will not make contestants lose money.

Input Format

There are 4 lines in total:

Line 1: m, representing the initial reward money given to each contestant;

Line 2: n, representing the number of OJ problems;

Line 3: n numbers, representing the deadlines for problems 1 to n;

Line 4: n numbers, representing the deduction amounts for problems 1 to n if not completed before their deadlines.

Output Format

Only 1 line. Represents the maximum amount of money Xiao Wei can earn.

```input1 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 ``` ```output1 9950 ``` ## Translation

Adapted Problem from "A Guide to Informatics Olympiad"

(Note: "信奥" is short for "信息学奥林匹克竞赛" (Informatics Olympiad), and "一本通" translates to "A Guide" or "A Comprehensive Book." The translation retains the concise and formal tone of the original while adapting it naturally for an English-speaking audience.)