### 问题描述 在数学课上，小桥开始突发奇想，思考各种各样的数学问题，他想到了这么一个问题。 给定一个长度为 $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_{i=l_x} ^{r_x} a_i$。 我们需要使得加权和值 $\sum _{i=1} ^k (W_i \times p_i)$ 最大。小桥将问题抛给了同桌小蓝，小蓝思考了之后仍然不会，他又把问题抛给了你。 你只思考了两秒钟，就知道了答案，你需要告诉小蓝答案是多少。 ### 输入格式 第一行输入两个整数 $n, k$。（$1 \le n \le 10^5, 1 \le k \le \min(n, 200)$）。 第二行输入 $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$）。 ### 输出格式 输出一个整数，代表最大加权和值。 ### 样例输入 ```bash 5 2 1 -2 4 3 -9 -1 4 ``` ### 样例输出 ```bash -7 ``` ### 说明 一种划分方法为：$\lbrace [1, 2], [3, 5] \rbrace$