题目描述

小慧准备参加湖南电视台举办的智力冲浪节目。规则如下： 冲浪者首先拥有m个快乐金球。冲浪当中设有n个游戏项目，每个游戏项目都必须在整分钟时开始，限时1分钟，而且都规定了最后完成的期限（即：冲浪开始后t分钟内必须完成）。如果一个游戏项目没按规定完成，则从冲浪者的快乐金球中扣掉一部分，不同游戏项目扣掉的金球数也不同。游戏项目的顺序自己安排。最终，赢得快乐金球数最多的选手胜出。 小慧非常想夺得冠军，请你计算了小慧最多能赢得多少个快乐金球？

输入

m n(m<=10000,n≤500) n个整数(以空格相隔)，分别表示每个游戏项目规定的完成期限（1≤ti≤n） n个整数(以空格相隔)，分别表示每个游戏项目末完成时扣掉的金球数

输出

一个整数（最多能赢得快乐金球的个数）

样例输入

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

样例输出

9950