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}$。

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

在第一个询问中，你需要将第二块木板的长度增加 $2$。所以你的总花费是 $2 \cdot b_2 = 2$。 在第二个询问中，你需要将第一块木板的长度增加 $1$，第三块木板的长度增加 $1$。所以你的总花费是 $1 \cdot b_1 + 1 \cdot b_3 = 9$。 在第三个询问中，栅栏本身就是“完美的”，所以你不需要花费卢布。 由 ChatGPT 4.1 翻译