假设给定一个n个不同关键字的严格升序序列K=<k[1], k[2], …, k[n]>，用这些关键字构造二叉搜索树。对关键字k[i]，有p[i]次被检索到。有些搜索的值可能不在K中，假设n+1个伪关键字D=<d[0], d[1], …, d[n]>，对i=1, 2, ..., n-1，d[i]表示在k[i]和k[i+1]之间的值，d[0]表示小于k[1]的值，d[n]表示大于k[n]的值。对每个伪关键字d[i]，有q[i]次被检索到。请注意这里规定了每个关键字和伪关键字的检索次数。
用上述D序列作叶节点，K序列做内部节点，（可以参考算法导论第三版中文版226-230页，但注意题目定义的不同之处）构造一棵最优二叉搜索树。假设根节点深度为1，给定p, q，求出这二叉搜索棵树的最小总代价。
总代价定义为下面两式之和： $$ \sum\limits_{i=1}^{n} depth(k[i]) \times p[i] $$
$$ \sum \limits_{i=0}^{n} depth(d[i]) \times q[i] $$
第一行两个整数n。$ 1 \le n \le 500 $
第二行n个整数 $ p[i] $，表示关键字的出现次数。
第三行n+1个整数$ q[i] $，表示i-1关键字与i关键字之间的出现次数。$ 0 \le p[i], q[i] \le 1000 $
一个整数，表示最小总代价。
5
15 10 5 10 20
5 10 5 5 5 10275