CF1221D Make The Fence Great Again

题目描述

你有一个由 $n$ 块竖直木板组成的栅栏。每块木板的宽度为 $1$。第 $i$ 块木板的高度为 $a_i$。如果没有任意一对相邻的木板高度相同，你认为这个栅栏是“完美的”。更正式地说，只有当对于所有从 $2$ 到 $n$ 的下标，条件 $a_{i-1} \neq a_i$ 都成立时，这个栅栏才是“完美的”。

不幸的是，现在你的栅栏可能不是“完美的”。但你可以进行修改！你可以将第 $i$ 块木板的长度增加 $1$，但你需要为此支付 $b_i$ 卢布。每块木板的长度可以增加任意次（也可以不增加）。

请计算，为了让栅栏再次变得“完美”，你最少需要花费多少卢布！

你需要回答 $q$ 个独立的询问。

输入格式

第一行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$），表示询问的数量。

每个询问的第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示栅栏的木板数量。

每个询问接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），分别表示第 $i$ 块木板的长度和每增加 $1$ 单位长度所需的价格。

保证所有询问中 $n$ 的总和不超过 $3 \cdot 10^5$。

保证每个询问的答案不超过 $10^{18}$。

输出格式

对于每个询问，输出一个整数，表示让栅栏变得“完美”所需花费的最小卢布数。

3
3
2 4
2 1
3 5
3
2 3
2 10
2 6
4
1 7
3 3
2 6
1000000000 2

2
9
0

说明/提示

在第一个询问中，你需要将第二块木板的长度增加 $2$。所以你的总花费是 $2 \cdot b_2 = 2$。

在第二个询问中，你需要将第一块木板的长度增加 $1$，第三块木板的长度增加 $1$。所以你的总花费是 $1 \cdot b_1 + 1 \cdot b_3 = 9$。

在第三个询问中，栅栏本身就是“完美的”，所以你不需要花费卢布。

由 ChatGPT 4.1 翻译