#P18378. Degree Sequence 3

Degree Sequence 3

Degree Sequence 3

题目描述

在第二届 Universal Cup 半决赛期间,你在奇琴伊察发现了一些古代玛雅人研究图论的记录,其中记载着一些树的度数序列。

后来,在 2024 年贵安 ICPC 集训营中,你或许已经做过 Degree Sequence 2。小青鱼很想向你介绍那道题,但是它可能会作为第四届 Universal Cup 的常规场次出现,因此他暂时不能透露。

不过,不必失望!谁说必须先做 Degree Sequence 2,才能挑战 Degree Sequence 3 呢?

回顾度数序列的定义:对于一张有 nn 个顶点的简单无向图,记顶点 ii 的度数为 did_i,即与该顶点关联的边数。那么整数序列 d1,d2,…,dnd_1,d_2,\ldots,d_n 就称为这张图的度数序列。简单图不允许重边或自环。

一张图及其各顶点度数与度数序列

如果存在一张简单无向图,其度数序列恰好为整数序列 aa,则称 aa 是一个合法度数序列。例如,(3,4,2,2,1,2)(3,4,2,2,1,2) 是合法度数序列,上图就是一种实现。

现在,小青鱼给你两个长度为 nn 的整数序列 a,ba,b。他希望将 aa 变为一个简单无向图的合法度数序列。为此,他可以执行任意多次以下操作:

  • 选择一个下标 1≤i≤n1\le i\le n,令 ai←ai−1a_i\leftarrow a_i-1,花费 bib_i 元。
  • 选择一个下标 1≤i≤n1\le i\le n,令 ai←ai+1a_i\leftarrow a_i+1,同样花费 bib_i 元。

请你求出所需的最小总费用。

目标图的顶点数仍为 nn,不要求连通,也不要求是一棵树。只需输出最小费用,无须输出目标图或操作方案。

输入格式

输入包含多组测试数据。第一行包含整数 TT(T≥1T\ge1),表示测试数据组数。

对于每组测试数据:

第一行包含整数 nn(1≤n≤1051\le n\le10^5)。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤n0\le a_i\le n),表示初始序列。注意,初始值可以等于 nn。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n(1≤bi≤1091\le b_i\le10^9),表示每次对相应位置增减 11 的费用。

保证所有测试数据的 nn 之和不超过 10610^6。

输出格式

对于每组测试数据,输出一行一个整数,表示将 aa 变为合法度数序列的最小总费用。

样例输入

3
3
2 1 1
100 1000 10000
3
2 1 0
100 10 1
5
1 2 3 4 5
1 10 100 1000 10000

样例输出

0
1
10002

样例说明

第一组数据无需执行操作,因为 (2,1,1)(2,1,1) 已经是合法度数序列。一种实现如下。

样例一的三个顶点及两条边

第二组数据,最优方案是令 a3←a3+1a_3\leftarrow a_3+1,得到 (2,1,1)(2,1,1),总费用为 b3=1b_3=1。

第三组数据,最优方案是先令 a5←a5−1a_5\leftarrow a_5-1,再对 a1a_1 执行两次加 11,得到 (3,2,3,4,4)(3,2,3,4,4),总费用为 2b1+b5=100022b_1+b_5=10002。目标序列的一种实现如下。

样例三中度数为三二三四四的五顶点图