冲浪

题目描述

冲浪大师睿睿打算冲浪 $n$ 分钟，每分钟内他可以选择一朵浪花冲上去站 $1$ 分钟，站满 $1$ 分钟后，这朵浪花就会消散于大海中，睿睿需要换一朵浪花，否则他就会掉进海里。 最开始有 $m$ 朵浪花，就算睿睿不站上去，浪花会在某个时刻自然消散，第 $i$ 朵浪花会在第 $a_i$ 分钟结束时消散。每朵浪花能带给睿睿的快乐是不同的，站在第 $i$ 朵浪花上会给睿睿带来 $b_i$ 的快乐。 如果睿睿掉进了海里，那么他之前获得的快乐都会消失，他需要从 $0$ 开始重新积累快乐。 求睿睿 $n$ 分钟结束时的最大快乐值。

输入格式

从标准输入读入数据。 第一行输入两个正整数 $n$（$n\le500$）和 $m$（$m\le2000$）。 第二行输入 $m$ 个正整数 $a_i$（$a_i\le n$）。 第三行输入 $m$ 个正整数 $b_i$（$b_i\le1000$）。

输出格式

输出到标准输出。 输出一个整数，表示最大快乐值。

样例 #1

样例输入 #1

6 8
4 2 6 2 6 1 1 6
13 14 5 7 4 3 8 1

样例输出 #1

45

提示

样例1解释

一种最优的浪花安排为（浪花的格式为 $(a_i,b_i)$）： $(1,8),(2,14),(6,1),(4,13),(6,4),(6,5)$