让栅栏再次美丽

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

你有一个由 $n$ 块竖直木板组成的栅栏，每块木板的宽度为 $1$，第 $i$ 块木板的高度为 $a_i$。当任意两块相邻木板的高度都不相同时，栅栏是美丽的。也就是说，对于所有 $2\le i\le n$，都应满足 $a_{i-1}\ne a_i$。

你可以把第 $i$ 块木板的高度增加 $1$，每增加一次需要支付 $b_i$ 卢布。每块木板可以增加任意次，也可以不增加。

请计算使栅栏变得美丽所需的最小总费用。你需要回答 $q$ 个相互独立的询问。

输入格式

第一行包含一个整数 $q$，表示询问数。

对于每个询问，第一行包含一个整数 $n$，表示木板数。接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i,b_i$，分别表示第 $i$ 块木板的初始高度和每增加一个单位高度的费用。

输出格式

对于每个询问输出一行一个整数，表示使栅栏变得美丽所需的最小费用。

样例输入 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\times b_2=2$。

第二个询问中，把第一块和第三块木板的高度各增加 $1$，费用为 $b_1+b_3=9$。

第三个询问中的栅栏已经满足要求，所以费用为 $0$。

数据范围

• $1\le q\le 3\times 10^5$；
• $1\le n\le 3\times 10^5$；
• $1\le a_i,b_i\le 10^9$；
• 所有询问的 $n$ 之和不超过 $3\times 10^5$；
• 每个询问的答案不超过 $10^{18}$。