← 返回题目列表

Codeforces · 1221/D

D. 让栅栏再次伟大

中文机器翻译题面 查看原题

你有一个由 $$$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$$$ 行包含板的描述。第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) — 分别是第 $$$i$$$ 板的长度和增加 $$$1$$$ 的价格。

保证所有查询的所有 $$$n$$$ 之和不超过 $$$3 \cdot 10^5$$$。

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

输出

对于每个查询,打印一个整数 - 为了使栅栏变得伟大而必须花费的最少卢布数。

示例

输入 #1

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

输出 #1

2
9
0

注意

在第一个查询中,您必须将第二块板的长度增加 $$$2$$$。因此,如果 $$$2 \cdot b_2 = 2$$$,则您的总成本。

在第二个查询中,您必须将第一块板的长度增加 $$$1$$$,将第三块板的长度增加 $$$1$$$。因此,如果 $$$1 \cdot b_1 + 1 \cdot b_3 = 9$$$,则您的总成本。

在第三个查询中,栅栏最初很棒,因此您不需要花费卢布。