← 返回题目列表

Codeforces · 730/E

E. 颁奖典礼

中文机器翻译题面 查看原题

全伯兰编程大赛落下帷幕。共有n支队伍参加。与 ACM-ICPC 一样,当前结果在比赛结束前一小时停止刷新。所以在颁奖典礼上,结果已经部分可知。对于每个团队,给出值 ai — 第 i 个团队在比赛最后一小时之前获得的分数。除此之外,评审团评估了最后一小时内发送的所有提交内容,并知道值 di — 第 i 个团队在最后一小时内获得的分数(这些值可以是负数,这意味着团队可能会失去分数)。

比赛前,每支队伍获得从1到n的唯一id。根据比赛规则,积分多的球队名次较高。如果两支或两支以上队伍积分相同,则id较低的队伍获得较高的名次。所以没有两支球队可以共用同一个位置。

颁奖典礼按以下方式进行。仪式开始时,大屏幕显示“结束前一小时”时间时刻的成绩,这意味着第i支队伍拥有ai分。然后评审团按照一定的顺序逐一解冻各队的成绩。当第j支队伍的成绩解冻后,其得分由aj变为aj+dj。此时成绩表已修改,球队名次也可能发生变化。第 j 队解冻后,观众报以|xj - yj| 的掌声。秒,其中 xj 是第 j 队解冻前的位置,yj 是解冻后的位置。例如,如果球队不改变地点,观众就不会鼓掌。正如您所看到的,在颁奖典礼期间,每个团队将被解冻一次。

你的任务是找到这样一个命令来解冻所有团队,使掌声的总持续时间尽可能长。

输入

输入文件的第一行包含一个整数 n (1 ≤ n ≤ 100) — 球队数量。

接下来的 n 行中的每一行都包含两个整数 ai 和 di (1 ≤ ai ≤ 100, - 100 ≤ di ≤ 100) — 第 i 队在比赛最后一小时之前获得的积分以及该队在最后一小时内获得的积分。解冻后球队有可能出现负分。

输出

打印唯一的整数 - 如果陪审团可以选择解冻团队的任何顺序,则最大总掌声持续时间(以秒为单位)。

示例

输入 #1

4
17 -14
52 -5
1 52
6 0

输出 #1

4

输入 #2

5
4 5
3 2
5 -3
6 -2
4 3

输出 #2

14

注意

在第一个示例中,初始排名为:

1.第2队,52分
2.第1队,17分
3.第4队,6分
4. 第 3 队,1 分

在此,任何解冻队伍的命令都会导致总共 4 秒的掌声。例如,让我们按照从团队 1 到团队 4 的顺序解冻团队。

1队解冻后积分榜为:

1.第2队,52分
2.第4队,6分
3. 第 1 队,3 分
4. 第 3 队,1 分

所以掌声有1秒,因为新旧地方的区别|2 - 3| = 1。

2队解冻后积分榜为:

1.第2队,47分
2.第4队,6分
3. 第 1 队,3 分
4. 第 3 队,1 分

二队的位置没有改变,所以解冻时没有掌声。

第3队解冻后积分榜为:

1.第3队,53分
2.第2队,47分
3.第4队,6分
4. 第 1 队,3 分

第3队的名次由4变为1,因此掌声时长为|4 - 1| = 3。

第 4 队的解冻没有改变任何地方,因为 d4 = 0。

因此,掌声的总持续时间为 1 + 0 + 3 + 0 = 4 秒。