CF1221D.Make The Fence Great Again

You have a fence consisting of $n$ vertical boards. The width of each board is $1$. The height of the $i$-th board is $a_i$. You think that the fence is great if there is no pair of adjacent boards having the same height. More formally, the fence is great if and only if for all indices from $2$ to $n$, the condition $a_{i-1} \neq a_i$ holds.

Unfortunately, it is possible that now your fence is not great. But you can change it! You can increase the length of the $i$-th board by $1$, but you have to pay $b_i$ rubles for it. The length of each board can be increased any number of times (possibly, zero).

Calculate the minimum number of rubles you have to spend to make the fence great again!

You have to answer $q$ independent queries.

你有一道由 $n$ 块竖直木板组成的篱笆。每块木板的宽度均为 $1$，第 $i$ 块木板的高度为 $a_i$。当不存在任意一对相邻木板具有相同高度时，你认为这道篱笆是“优秀的”。更准确地说，篱笆是优秀的当且仅当对所有从 $2$ 到 $n$ 的下标 $i$，均满足 $a_{i-1} \neq a_i$。

不幸的是，当前你的篱笆可能并不优秀。但你可以对其进行修改！你可以将第 $i$ 块木板的高度增加 $1$，但需为此支付 $b_i$ 卢布。每块木板的高度可被增加任意多次（包括零次）。

请计算使篱笆再次变得优秀所需支付的最少卢布数！

你需要回答 $q$ 个相互独立的查询。

The first line contains one integer $q$ ($1 \le q \le 3 \cdot 10^5$) — the number of queries.

The first line of each query contains one integers $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of boards in the fence.

The following $n$ lines of each query contain the descriptions of the boards. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^9$) — the length of the $i$-th board and the price for increasing it by $1$, respectively.

It is guaranteed that sum of all $n$ over all queries not exceed $3 \cdot 10^5$.

It is guaranteed that answer to each query will not exceed $10^{18}$.

第一行包含一个整数 $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}$。

For each query print one integer — the minimum number of rubles you have to spend to make the fence great.

对于每个查询，输出一个整数——使围栏变得“优秀”所需的最少卢布数。

In the first query you have to increase the length of second board by $2$. So your total costs if $2 \cdot b_2 = 2$.

In the second query you have to increase the length of first board by $1$ and the length of third board by $1$. So your total costs if $1 \cdot b_1 + 1 \cdot b_3 = 9$.

In the third query the fence is great initially, so you don't need to spend rubles.

在第一次查询中，你需要将第二块木板的长度增加 $2$。因此，你的总花费为 $2 \cdot b_2 = 2$。

在第二次查询中，你需要将第一块木板的长度增加 $1$，并将第三块木板的长度增加 $1$。因此，你的总花费为 $1 \cdot b_1 + 1 \cdot b_3 = 9$。

在第三次查询中，围栏初始状态即为“优秀”，因此你无需花费卢布。