暴力求和

题目描述

序列 $a$ 长度为 $N$为 $a_1,a_2...a_n$.$(-10^6 \le a_i \le 10^6)$ 序列 $b$ 长度为 $K$为 $b_1,b_2...b_k$$(-10^6 \le b_i \le 10^6)$. 从$a$中取出长度为$K$的子序列 $c$ 记为$c_1,c_2...c_k$. 求$\sum_{i=1}^{k}b_ic_i+\sum a -\sum c$的最小值。

子序列是指从给定序列中去除一些元素（也可能不去除）后，剩余元素组成的序列。重要的是，这个过程中剩余元素的相对顺序保持不变。例如，对于序列 [1,2,3,4,5,6]，[2,3,6],[2,3,4],[2,4,6] 就是一个可能的子序列.

输入格式

第一行输入一个正整数$N$$(1 \le N \le 10^6)$。 第二行输入$N$个数代表$a_1,a_2...a_n$.$(-10^6 \le a_i \le 10^6)$ 第三行输入一个正整数$K$$(1 \le K \le 20)$ 第四行输入$K$个数代表$b_1,b_2...b_k$$(-10^4 \le b_i \le 10^4)$.

输出格式

第一行输出一个整数代表最小值

样例 #1

样例输入 #1

4
4 1 3 2
3
4 2 3

样例输出 #1

20

提示

Python提交建议选择pypy3，并选择空间复杂度更小的做法。