说明

给定$n$个关键字组成的有序序列$S={s_1，s_2，…，s_n}$，关键字结点称为实结点。对每个关键字查找的概率是$p_i$，查找不成功的结点称为虚结点，对应${e_0，e_1，…，e_n}$，每个虚结点的查找概率为$q_i$。$e_0$表示小于$s_1$的值，$e_n$大于$s_n$的值。所有结点查找概率之和为1。求最小平均比较次数的二叉搜索树（最优二叉搜索树）。

举例说明：给定一个有序序列$S={5，9，12，15，20，24}$，这些数的查找概率分别是$p_1、p_2、p_3、p_4、p_5、p_6$。在实际中，有可能有查找不成功的情况，例如要在序列中查找x=2，那么就会定位在5的前面，查找不成功，相当于落在了虚结点$e_0$的位置。要在序列中查找x=18，那么就会定位在15～20，查找不成功，相当于落在了虚结点$e_4$的位置。

输入格式

第一行是一个整型数$m(m<100)$表示共有$m$组测试数据。

每组测试数据第一行输入$n（1 <= n <=20）$为关键字个数。

第2行输入$n$个数，代表每个关键字的搜索概率$p_i（0 <= p_i <=1，且∑p_i+∑q_i=1）$。

第3行输入$n+1$个数，代表每个虚结点的搜索概率$q_i（0 <=q_i <=1，且∑p_i+∑q_i=1）$。

输出格式

对于每一组输入，输出最优二叉搜索树的搜索成本。

每组的输出占一行。

样例

2
6
0.04 0.09 0.08 0.02 0.12 0.14
0.06 0.08 0.10 0.07 0.05 0.05 0.10
4
0.05 0.1 0.3 0.08
0.2 0.06 0.01 0.13 0.07

2.52
1.87

来源

《趣学算法》4.10节