题目内容

培养箱里从左到右装了一排探头。第 $i$ 个探头现在的刻度是正整数 $v_i$。可以把任意探头改成别的非负整数，改第 $i$ 个需要付维修费 $c_i$，不改就不付钱。

改完以后，整排刻度必须同时满足两条：

• 从左到右不下降，后一个不小于前一个；
• 相邻两个的差全程相同。

也就是说，存在两个非负整数：起点 $s$ 和公差 $d$，使第 $i$ 个探头的最终刻度正好是 $s+(i-1)\cdot d$。请为每一组探头算出最少维修费。

输入描述

第一行一个整数 $q$，表示巡检组数。

接下来 $q$ 行，每行先是该组探头数 $m$，接着 $m$ 个维修费 $c_1,c_2,\dots,c_m$，再接着 $m$ 个当前刻度 $v_1,v_2,\dots,v_m$。

$1 \le q \le 2 \times 10^5$

$1 \le m \le 2 \times 10^5$

$1 \le v_i \le m$

$1 \le c_i \le 10^9$

所有组的 $m$ 加起来不超过 $2 \times 10^5$。

维修费累加后可能超出 $32$ 位有符号整数，计算时使用 $64$ 位整数。

输出描述

输出一行，共 $q$ 个整数，依次是每组的最少维修费，相邻两个用一个空格分开。

样例1

输入

2
5 7 8 9 1 2 1 2 3 4 5
4 3 5 3 5 1 4 1 4

输出

0 6

说明

第一组已经是起点 $1$、公差 $1$ 的刻度，不用改。

第二组改成 $4,4,4,4$：两个 $1$ 都要改，费用 $3+3=6$。改成 $1,1,1,1$ 要付 $5+5=10$，更贵。

样例2

输入

1
1 100 1

输出

0

说明

只有一个探头时，没有相邻差要满足，保持原刻度即可。

样例3

输入

1
3 4 10 1 3 1 2

输出

4

说明

取起点 $0$、公差 $1$，目标是 $0,1,2$。只有第一个探头从 $3$ 改成 $0$，费用 $4$。后两个本来就是 $1$ 和 $2$。