#2251. 盒子

    ID: 2251 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest3434来源:qoj.ac数据:公开样例动态规划枚举

盒子

盒子

题目描述

标题: 盒子 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

sk 有 N 个漂亮的盒子,编号为 1∼N。第 i 个盒子有两个属性 Si 和 Pi,分别代表该盒子的大小和美丽程度。盒子 i 能够被放入所有满足 Si≤Sj 的盒子 j 中。

mxr 的生日要来了,于是 sk 打算给 mxr 送一些盒子作为生日礼物。因为送空盒子听起来不是很好,所以 sk 打算在盒子里面装其他盒子。具体地,sk 打算选择 K 对盒子,然后对每一对盒子,将某个盒子放到另一个里面(如果两个盒子的大小相同,他可以选择将哪个盒子放入另一个,否则他将小的那个盒子放入大的盒子中)。对每一对盒子 (i,j),如果盒子 i 在盒子 j 中,那么这一对盒子的美丽值为 Pj−Pi,因为 sk 觉得里面的盒子的美丽程度被浪费了。

由于拆盒子是一件很无聊的事,所以 mxr 可能不想要太多对盒子,并且 sk 不知道最理想的 K 值是多少。所以,对 1 到 ⌊n2⌋ 之间的每个 K,你需要帮 sk 找到他能用最多 K 对盒子得到的最高的总美丽值(即所有盒子对的美丽值之和的最大值)。

输入格式

第一行一个整数表示 N。

接下来 N 行每行两个整数表示 Si,Pi。

输出格式

输出 ⌊n2⌋行,第 i 行表示 k=i 时的答案。

样例一

input

5
1 4
1 5
1 3
3 4
3 1

output

3
5

限制与约定

对于 10% 的数据,N≤10。

对于 30% 的数据,N≤100。

对于 60% 的数据,N≤2×103。

对于 100% 的数据,1≤N≤2×105,1≤Si≤n,1≤Pi≤109。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
1 4
1 5
1 3
3 4
3 1
3
5