Description

Xiao Wei signed up for an OJ competition show. This challenge attracted many OIers, and to commend everyone's courage, the host first rewarded each participant 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 presented many beginner-level problems like A+B Problem, each of which 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 participant can complete it within one period, and all problems must start at the beginning of an integer period. The host simply wants to test how each participant 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 leave participants losing money.

Input Format

There are 4 lines in total:

Line 1: m, representing the initial reward money given to each participant.

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 they are 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 Problems from "A Guide to Informatics Olympiad"

(Note: "信奥" is short for "信息学奥林匹克竞赛" (Informatics Olympiad), and "一本通" translates to "A Guide" or "A Comprehensive Book." The title suggests this is a collection of adapted or modified problems from a well-known Informatics Olympiad preparation resource.)