题目描述

小泽初始有 $m$ 枚金币，要完成 $n$ 个小游戏，每个游戏耗时恰好一个时间单位。游戏 $i$ 若没能在第 $t_i$ 个时间单位结束前完成，就会扣除 $w_i$ 枚金币。每个游戏至多完成一次。求最终最多能保留多少金币。

输入格式

第一行整数 $m$，第二行整数 $n$，第三行 $n$ 个期限 $t_i$，第四行 $n$ 个扣款 $w_i$。

输出格式

输出最多能保留的金币数。

输入

500000
7
7 4 7 2 2 3 7
811 726 21 854 180 816 174

输出

500000

输入

500000
18
8 2 6 17 14 11 12 16 17 17 17 15 17 7 13 14 2 9
956 183 760 572 567 507 812 418 87 275 553 675 166 709 162 342 364 758

输出

499913

输入

500000
20
13 13 11 1 17 5 2 18 3 10 8 2 9 11 4 10 4 18 8 19
939 821 40 50 20 105 416 295 915 341 86 743 41 965 795 94 628 695 529 725

输出

499494

数据范围

$1\le n\le500$，$1\le m\le5\times10^5$，$1\le t_i\le n$，$1\le w_i\le1000$。