You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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 翻译