#k. 奶牛叠叠乐

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

谢苗家是诺夫哥罗德有名的牛奶生产商，传说他家的奶牛非常聪明，连带产出的牛奶也有增进智力的作用。

（以上纯属瞎扯）

谢苗家总共有 $N$ 头奶牛，编号 $1$ 到 $N$ 。当奶牛 $i$ 站在地面上时，肩高为 $A_i$ ，头高为 $B_i$ 。

谢苗诺夫想把这些奶牛堆叠起来，拍一张特别浮夸的广告照，他需要这样做：

选择一头奶牛放在地上。令其编号为 $x$ ，那么她的肩离地的高度是 $A_x$ ，头离地的高度是 $B_x$ 。
选择另一头奶牛，将其放在奶牛 $x$ 的肩上。令其编号为 $y$ ，那么她的肩离地的高度是 $A_x + A_y$ ，头离地的高度是 $A_x + B_y$ 。

显然，谢苗诺夫总共有 $N!$ 种不同的堆叠奶牛的方法。他现在想知道，所有的堆叠奶牛的方中，处于最上方的奶牛的头离地的最大高度。

输入格式

第一行有一个数，为奶牛的个数 $N$ 。

接下来每一行两个数，其中第 $i$ 行分别为 $A_{i-1}$ 和 $B_{i-1}$ 。

输出格式

一个数，为最后的最大高度。

可以选择放第 3头奶牛在最上面
第一头奶牛肩高 4 + 第二头奶牛肩高 5， 4+5=9
第三头奶牛踩在前两头奶牛上面，所以第三头奶牛头高是 9+9=18

10
690830957 868532399
741145463 930111470
612846445 948344128
540375785 925723427
723092548 925021315
928915367 973970164
563314352 832796216
562681294 868338948
923012648 954764623
691107436 891127278

7362669937

数据范围

$2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
$1\ \leq\ A_i\ \leq\ B_i\ \leq\ 10^9$

寒假刷题联合训练88题

未参加

状态: 已结束
规则: IOI
题目: 85
开始于: 2025-1-8 15:00
结束于: 2025-1-8 16:00
持续时间: 1 小时
主持人: root
参赛人数: 246