题目描述

暑期集训马上就结束了，但是训练显然不能就这么结束，所以你决定在接下来的 $n$ 天内规划你新一轮训练。

这 $n$ 天内，每天训练都可以获得一些经验值，第$i$天训练可以获得 $a_i$ 的经验值。

此外，集中的训练总是比分散的训练更加有效。具体来说，你希望将连续数天（至少一天）规划为一段计划，在这段计划中，第 $j$ 天获得的经验值将变为原来的 $b_j$ 倍。连续的天数不宜过长，所以一段计划持续的天数不能超过 $m$ 天。在一段计划结束后，你希望为自己安排至少一天的休息时间。休息时间不训练，当然也不会获得经验值。 休息过后，你就可以开始下一段计划了。（注意，第一段计划开始前也可以选择休息）

在以上的情况下，接下来 $n$ 天你最多能获得多少经验值？

输入格式

第一行输入两个正整数 $n,m$ $(1\le n\le 10^3,1\le m\le 100)$ 。

第二行输入 $n$ 个数，代表数组 $a$，第 $i$ 天获得的基础经验值为$a_i$ $(1\le a_i\le 10^4)$。

第三行输入 $m$ 个数，代表数组 $b$ ，在一段计划的第 $i$ 天获得的经验值将变为原来的 $b_i$ 倍。$(1\le b_i\le 100)$

输出格式

输出一行一个整数，代表接下来$n$天最多能获得的经验值。

输入输出样例 #1

6 4
1 5 3 4 2 6
2 1 2 3

37

输入输出样例 #2

5 5
1 3 1 3 1
3 1 3 1 5

20

解释与说明

样例2中选择第一天休息，后面四天为一段计划可以获得最大经验值。