OJ现已增加邮箱找回密码功能,还没有绑定邮箱的同学们请抓紧时间,以免密码丢失无法找回


问题1373--试图赎罪的包工头

1373: 试图赎罪的包工头

时间限制: 2 Sec  内存限制: 128 MB
提交: 64  解决: 40
[提交] [状态] [讨论版] [命题人:]

题目描述



包工头最近又在为一道难题犯难,现在他想奖励你一摞票子,希望你能帮他解决这个问题。
现在包工头有一个空的集合S,然后按顺序执行q条指令,每条指令的格式为 op x,表示:
若op = 0,则表示向集合S中插入元素x。
若op = 1,则表示需要从集合S中选择一个合适的数字y,然后包工头会得到abs(y-x)的惩罚,并且这个数字y将从S中永久删除。
在完成q次操作后,规定包工头得到的惩罚总和为sum,但他并不想得到更多的惩罚,所以希望你能使得sum尽可能小。

输入

第一行一个数字q,表示执行操作的数量。(1 ≤ q ≤ 500)
接下来q行,每行两个数字 op,x,表示操作类型和权值(0 ≤ op ≤ 1,1 ≤ x ≤ 1000000000)。
样例保证在执行op = 1类型操作时,集合S必定存在元素。

输出

一个整数sum,表示包工头得到的最小的惩罚。

样例输入 Copy

4
0 3
0 5
1 4
1 6

样例输出 Copy

2

来源/分类