← 返回比赛

已结束 GESP欢乐赛#60

← 上一题下一题 →

A6061 | $人气比拼$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

动物园内有两个势力，分别是狮子作为首领的狮子帮，以及老虎作为首领的老虎帮。 现在动物园里一共有 $n$ 只动物，每只动物都有自己的人气值 $v_i$，并且每只动物都归属于两个势力其中之一。一个势力的人气值为势力内所有动物人气值的总和。 小明不希望两个势力的人气值太过于悬殊，因此他可以执行最多一次操作（也可以不执行）：小明会选择一只动物，使得它改换到另一个阵营。问最终人气值的差值最小是多少？

输入格式

第一行输入一个整数 $n$, 代表动物园内动物的总数 $(10 \le n \le 10^5)$。 接下来 $n$ 行， 每行两个数字 $v_i, t_i(1 \le v_i \le 10^4, 0 \le t_i \le 1)$， 分别代表人气值和所属的势力， $t_i = 0$时候该动物属于狮子帮， $t_i = 1$ 时该动物属于老虎帮。

输出格式

输出一个整数，代表最小的人气值差距。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出