解题思路

核心模型：带负权值的 0/1 背包（最小费用）

目标是从若干个 $a_i$ 中选出一部分，使得 $\sum a_i = 1$，并且 $\sum b_i$ 最小。 这是一个 和为指定值的子集选择问题，与 0/1 背包类似，但权值（这里是“电量”）可为负数。

状态设计

• 设 $S=\sum |a_i| \le 6000$。可能的电量和范围为 $[-S, S]$。

题目内容

小红接触到了一款城市建设的游戏。在这个游戏玩家需要建造很多的设施。其中一些设施可以提供电力，而另一些则会消耗电力。每种设施均只能建造至多一个。且建造设施还需要花费一定的资金。

如果某一时刻剩余电量(即所有发电设施产生的电力减去其他设施消耗的电力)恰好为 $1$ ，则可以获得《高手电量》这一稀有成就。小红现在希望获得这一成就，请你帮他计算，如何才能在花费最少资金的情况下达成这一成就。

输入描述

输入的第一行包含一个数 $n(1<=n<=3000)$ ，表示小红可以建造 $n$ 种不同的设施。

接下来的 $n$ 行，每行包括两个整数 $a_i,b_i$ ;，表示建造第 $i$ 种设施可以带来 $a_i$ 的电力(如果 $a_i< 0$ 则表示消耗 $|a_i|$ 的电力)，但需花费 $b_i$ 的金额建造。

数据保证所有输入均为整数，$|a_i|< 3000，1<=b_i<=10^4$ ，且 $a_i$ 之和的绝对值不超过 $6000$ 。

输出描述

如果无法做到剩余电量为 $1$ ，则输出 $-1$ ;

如果可以，则输出所需花费的最小资金。

样例1

输入

4
8 1
-4 2
-2 3
-1 4

输出

10

样例2

输入

2
6 3
-2 2

输出

-1