糖果商店

题目描述

一条街上有 $n$ 家糖果商店，按小灰灰经过的顺序编号为 $1,2,\ldots,n$．第 $i$ 家商店出售第 $a_i$ 种糖果，每颗售价为 $c_i$ 元．不同商店可能出售同一种糖果．

小灰灰最初没有糖果．他将依次经过这 $n$ 家商店，每经过一家商店，可以选择以下三种操作之一：

1. 花费 $c_i$ 元，购买一颗第 $a_i$ 种糖果．
2. 从自己当前持有的糖果中，拿出一颗种类不是 $a_i$ 的糖果，免费换取一颗第 $a_i$ 种糖果．交出的糖果不再归小灰灰所有．
3. 不进行任何操作．

每家商店最多只能购买一颗糖果或交换一次，不能既购买又交换．离开一家商店后，不能返回．小灰灰可以持有多颗同一种糖果，也可以将之前换来的糖果用于后续交换．

小灰灰希望经过所有商店后，对于这些商店出售过的每一种糖果，自己手中都至少有一颗．请你求出他最少需要花费多少钱．

输入格式

第一行包含一个正整数 $n$，表示商店的数量．

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,c_i$，分别表示第 $i$ 家商店出售的糖果种类和每颗糖果的价格．糖果种类编号为正整数，价格为非负整数．

输出格式

输出一个整数，表示满足要求所需的最少花费．

样例 1

输入

3
1 1
1 2
2 100

输出

3

解释

一种最优方案如下：

• 在第 $1$ 家商店花费 $1$ 元，购买一颗第 $1$ 种糖果．
• 在第 $2$ 家商店花费 $2$ 元，再购买一颗第 $1$ 种糖果．
• 在第 $3$ 家商店拿出一颗第 $1$ 种糖果，换取一颗第 $2$ 种糖果．

最后，小灰灰持有第 $1$ 种和第 $2$ 种糖果各一颗，总花费为 $3$ 元．

样例 2

输入

3
1 10
2 1
2 1

输出

11

解释

只有第 $1$ 家商店出售第 $1$ 种糖果．经过这家商店时，小灰灰还没有糖果可用于交换，因此必须花费 $10$ 元购买一颗，并将其保留到最后．再花费 $1$ 元购买一颗第 $2$ 种糖果即可．

下发样例

• Data/sample1.in 与 Data/sample1.ans：题面中的样例 1．
• Data/sample2.in 与 Data/sample2.ans：题面中的样例 2．
• Data/sample3.in 与 Data/sample3.ans：$n=8$，满足子任务 1 的限制．
• Data/sample4.in 与 Data/sample4.ans：$n=2\times10^5$，满足子任务 2 的限制．
• Data/sample5.in 与 Data/sample5.ans：$n=2000$，满足子任务 3 的限制．
• Data/sample6.in 与 Data/sample6.ans：$n=2\times10^5$，该样例无特殊限制．
• Data/sample7.in 与 Data/sample7.ans：$n=2\times10^5$，该样例无特殊限制．

点击下载本题选手目录

数据规模与约定

对于所有数据，保证 $1\le n\le 2\times10^5$，$1\le a_i\le n$，$0\le c_i\le 10^9$．

本题采用捆绑测试．只有通过一个子任务中的所有测试点，才能获得该子任务的分数．

子任务编号	分数	$n\le$	特殊性质
1	15	$8$	无
2	20	$2\times10^5$	$c_1\le c_2\le\cdots\le c_n$
3	25	$2000$	无
4	40	$2\times10^5$