题目描述

你最初得到 $m$ 元奖金，有 $n$ 个游戏，每个游戏占用一个完整时段，从时刻 $0$ 开始依次安排。第 $i$ 个游戏必须在时刻 $t_i$ 及之前完成，否则扣去 $w_i$ 元。求最多能保留的奖金。

输入格式

第一行初始奖金 $m$。第二行游戏数 $n$。第三行 $n$ 个截止时刻。第四行 $n$ 个罚款金额。

输出格式

输出最多能保留的奖金。

样例

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

9950

数据范围

$1\le n\le500$，$1\le t_i\le n$，$0\le w_i\le10^6$，$0\le m\le10^9$。保证存在安排使最终奖金不为负数。