题目描述

你的任务是切割不同长度的铜棒，切割铜棒每次只切一段，成本是根据铜棒的长度而定，不同切割的顺序会有不同的成本。

例如：有一根10米长的铜棒必须在第2、4、7米的地方切割。你可以选择先切2米的地方，然后切4米的地方，最后切7米的地方，这样的选择其成本为：

10 + 8 + 6 = 24

因为第一次切时铜棒长10米，第二次切时铜棒长8米，第三次切时铜棒长6米。但是如果你选择先切4米的地方，然后切2米的地方，最后切7米的地方，其成本为：

10 + 4 + 6 = 20

显然这种切法就是一个较好的选择。

请找出切割一根铜棒所需的最小成本。

输入格式

• 第一行输入一个整数 n，表示切割点的数量。
• 第二行输入 n 个整数 c1, c2, ..., cn，表示铜棒的长度。
• 第三行输入一个整数 m，表示切割点的数量，接下来 m 行每行一个整数，表示每个切割点的位置。

输出格式

输出一个整数，表示切割铜棒的最小成本。

样例

输入样例 1

3
10 8 6
4
2
4
7

输出样例 1

20

输入样例 2

4
4 5 7 8
4
4
5
7
8

说明

在样例2中，切割处为 4, 5, 7, 8，求 dp[0][3] 即从 0 切割点到第 3 切割点这一段铜棒切割所需的最小代价时，有两种切法，即从 4 的位置切或者从 5 的位置切，这样将这一段铜棒分为前后两部分，而前后两部分的最小代价值已经算出。所以两部分的最小代价值加这一刀的代价值即为 dp[0][3] 的值。