题目描述

有 $n$ 份食材，每份食材最多烹调一次。烹调第 $i$ 份食材需要 $c_i$ 单位时间。如果它在时刻 $t$ 完成，将得到 $a_i-b_i t$ 的美味指数。

从时刻 $0$ 开始，任意时刻最多烹调一份食材。你可以选择食材及烹调顺序，也可以不烹调任何食材。所有选中的食材必须在时刻 $T$ 或之前完成。

求可以得到的最大美味指数之和。某份食材的美味指数可以为负数；不烹调任何食材时总美味指数为 $0$。

输入格式

第一行两个整数 $T,n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

第四行 $n$ 个整数 $c_1,c_2,\ldots,c_n$。

输出格式

输出一个整数，表示最大美味指数之和。

样例 1

输入

5 2
20 20
1 3
3 2

输出

29

说明

先烹调第 2 份食材，在时刻 $2$ 完成，得到 $20-3\times2=14$；再烹调第 1 份食材，在时刻 $5$ 完成，得到 $20-1\times5=15$。总美味指数为 $29$。

样例 2

输入

5 3
1 8 100
3 0 1
1 2 6

输出

8

说明

只烹调第 2 份食材，得到 $8$。第 1 份无论何时完成，美味指数均为负；第 3 份无法在规定时间内完成。

数据范围

对于所有数据，保证 $1\le n\le50$，$1\le T\le99999$，$0\le a_i,b_i\le99999$，$1\le c_i\le99999$，输入均为整数。

时间限制：2 秒；内存限制：256 MiB。建议使用 64 位整数计算乘积和总美味指数。