题目描述

禾木正在参加一场编程比赛，比赛为 m 分钟，共有 n 道题。禾木可以在完成任意一道编程题后提交代码，第 i 道题的初始分数为 ai，题目的分数随着比赛的进行，每分钟减少 bi, 完成第 i 道题需要 ci 的时间，假设所有的编程题禾木都会, 禾木完成第 i 道题需要 ci 的时间，请计算出禾木在这场比赛中最多能够得多少分？

输入格式

第 1 行包含两个正整数 m 和 n，表示比赛总时间和题目数量。 第 2 行包含 n 个正整数 ai，表示每道题的初始分数。 第 3 行包含 n 个正整数 bi，表示每道题每分钟减少的分值。 第 4 行包含 n 个正整数 ci，表示禾木完成每道题的需要的时间。

输出格式

1行，包含一个整数，表示禾木最多能够得到的分数。

样例1

30 2
200 300
10 15
5 6

300

样例2

75 3
250 500 1000
2 4 8
25 25 25

1200

数据范围

1 ≤ m ≤ 1000; 1 ≤ n ≤ 100； 1 ≤ ai ≤ 10000； 1 ≤ ci ≤ m; 1 ≤ ci ≤ ai; 1 ≤ bi ≤ ai / ci。