#9286. 「2025CSP-X」勇者斗恶龙(hero) 普及+/提高

为了拯救世界，勇者们终于来到了恶龙面前。

现在有 位勇者排成一列准备迎战恶龙，勇者们位置事先已经排好不能改变，第 位勇者的初始能力值为 ，且每提升 点能力值，需要花费 的代价。

但是如果任意相邻的两位勇者能力值相同，他们之间就会产生冲突从而导致战力大幅下降。

你可以通过提升勇者的能力值，来确保队伍中任意相邻的两名勇者能力值都不相同，从而以完美的状态迎接恶龙。

你只需要计算并输出满足条件所花费的最小的总代价。

第一行一个整数 ，表示勇士的数量。

接下来 行，每行两个数 ,; 分别表示第 位勇士的初始能力值和每提升 点能力值需要花费的代价。

一行一个整数表示答案。

样例输入 1

3
1 5
1 2
2 3

样例输出 1

4

样例解释 1 如果把第一个勇者能力值增加1，三位勇者的能力值变成(2,1,2)，花费代价5。

如果把第二个勇者能力值增加2，三位勇者的能力值变为(1,3,2)，花费代价4。

如果把第二个勇者能力值增加1，第三个勇者的能力值增加1，三位勇者的能力值变为(1,2,3)，花费代价 5。

因此最小花费的代价为4，可以证明没有更小的代价能满足条件。

样例输入 2

3
1 10
1 100
1 20

样例输出 2

30

样例解释 2 可以分别提升第一位和第三位勇士的能力值1点，最小总花费为30。

样例3 见选手目录下的 hero/ex hero3.in与hero/ex_ hero3.ans。

该样例满足数据范围中测试点第9~10的限制。

样例 4 见选手目录下的 hero/ex hero4,in与hero/ex_hero4.ans。

该样例满足数据范围中测试点第11~12的限制。

样例5 见选手目录下的 hero/exhero5.in与hero/ex_hero5.ans。

该样例满足数据范围中测试点第13~20的限制。

对于所有测试数据，保证：