解题思路

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

P3611.第1题-电力系统

2000ms

Difficulty: 5

所属公司 : 滴滴

算法与标签>动态规划

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

如果某一时刻剩余电量(即所有发电设施产生的电力减去其他设施消耗的电力)恰好为 $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$ ;

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

输入

输出

输入

2
6 3
-2 2

输出

-1

输入

预期输出（选填）