题目描述

赛罗拥有 \(m\) 点能量值去打小怪兽，他是这样战斗的： 首先，时间分为 \(n\) 个时段 \((n≤500)\)，对手是 \(n\) 个小怪兽，每个小怪兽都必须在规定期限 \(t_i\) 前打败 \((1≤t_i≤n)\)。如果一个怪兽没能在规定期限前击败，则要从 \(m\) 点能量中中扣去一部分能量 \(w_i\)，\(w_i\) 为自然数，不同的小怪兽扣掉的能量是不一样的。当然，每个小怪兽都很菜鸡，保证都能在一个时段内搞定。现在请你帮助赛罗安排打怪兽的顺序，让他能够最后保留最多的能量值。 另外，赛罗的能量值不可能变成负数。

格式

输入格式

输入共 \(4\) 行。

第一行为 \(m\)，表示一开始赛罗的能量值

第二行为 \(n\)，表示有 \(n\) 个小怪兽； 第三行有 \(n\) 个数，分别表示怪兽 \(1 \sim n\)的规定的打败时间；

第四行有 \(n\) 个数，分别表示小怪兽 \(1 \sim n\) 不能在规定期限前打败的话赛罗损失的能量值。

输出格式

仅 \(1\) 行。表示赛罗最多能保留多少能量。

样例1

样例输入1

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

样例输出1

9950

来源

地址：\(\text{Online~Judge}\)
作者：征宇
模拟赛\(T2\)