未命名

中文题面来自算法竞赛入门经典

你是一个匹萨店的老板，有一天突然收到了 $n$ 个客户的订单（$n\le 100$）。你所在的小镇只有一条笔直的大街，其中位置 $0$ 是你的匹萨店，第 $i$ 个客户的家在位置 $p_i$。如果你选择给第 $i$ 个 客户送餐，他将会支付你 $e_i-t_i$ 元，其中 $t_i$ 是你到达他家的时刻。当然，如果你到的太晚，使得 $e_i-t_i<0$，你可以路过他家但是不进去给他送餐，免得他反过来找你要钱。

你只有一个送餐车，因此只能往返地送餐，如图所示就是一个路线。图中的第一行 是位置，第二行是 $e_i$。图上的路线对应的总收益为 $12$（$c4$ 付 $3$ 元，$c2$ 付 $3$ 元，$c5$ 付 $5$ 元，$c1$ 付 $1$ 元）。

不过图所示路线并不是最优的。最优路线是 $0->c3->c2->c1->c5$，总收益是 $32$。你的任务是求出最大收益。

输入

第一行为数据组数T。接下来每组中： 第一行为 $n$ 个客户, 第二行共 $n$ 个 $p_i$ 代表第 $i$ 个客户相对披萨店的位置, 第三行共 $n$ 个 $e_i$ 代表第 $i$ 个客户会付给你的钱。

输出

在一行中输出你能获得的最大收益。

样例

样例输入

3
5
-6 -3 -1 2 5
27 10 2 5 20
6
1 2 4 7 11 14
3 6 2 5 18 10
11
-14 -13 -12 -11 -10 1 2 3 4 5 100
200 200 200 200 200 200 200 200 200 200 200
 

样例输出

32
13
1937

思路

代码