问题描述

在数学课上，小桥开始突发奇想，思考各种各样的数学问题，他想到了这么一个问题。

给定一个长度为 $n$ 的序列 $\lbrace a_1, a_2, a_3, ..., a_n \rbrace$，以及一个长度为 $k$ 的序列 $\lbrace p_1, p_2, ..., p_k \rbrace$。

需要划分出 $k$ 个区间$\lbrace [l_1, r_1], [l_2, r_2], ... ,[l_k, r_k] \rbrace$，满足以下要求：

1. $l_1 = 1$ 以及 $r_k = n$。

2. $l_i \le r_i$。

3. 当 $i \lt k$ 时，$r_i + 1 = l_{i+1}$。

   我们定义每个区间的权值为这个区间的和值，即：$W_x = \sum\limits_{i=l_x} ^{r_x} a_i$。

   我们需要使得加权和值 $\sum _{i=1} ^k (W_i \times p_i)$ 最大。小桥将问题抛给了同桌小蓝，小蓝思考了之后仍然不会，他又把问题抛给了你。

   你只思考了两秒钟，就知道了答案，你需要告诉小蓝答案是多少。

输入格式

第一行输入两个整数 $n, k$。

第二行输入 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$。（$-1 0^6 \le a_i \le 10^6$）。

第三行输入 $k$ 个整数 $p_1, p_2, ..., p_k$。（$-10^6 \le p_i \le 10^6$）。

输出格式

输出一个整数，代表最大加权和值。

样例输入输出

5 2
1 -2 4 3 -9
-1 4

-7

说明

一种划分方法为：$\lbrace [1, 2], [3, 5] \rbrace$。

评测用例规模与规定

对于$10\%$的数据，$1 \le n \le 200, 1 \le k \le \min(n, 200)$。

对于$100\%$的数据，$1 \le n \le 10^5, 1 \le k \le \min(n, 200)$​。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$256M$