神犇传说

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

背景

Zyq 写过一本《犇记》,是世界上第 \(\inf\) 本纪传体通史。

描述

其中记载了一个神犇:Leaiser。

书曰:“Leasier是一神犇,其数论甚orz,尝与IOI,几深所钟而AK矣,尝集训队,以集训队吊在地打,实orz极,而其尤orz者,见一道题,则知己须数日深所钟思,几深所钟敲代码。故乃IOI犹ACM,其皆得妙策来AK 。”

~~小问号你是否有很多朋友?~~

现在你得到了 Leasier 神犇的帮助,他决定帮助你 AK 这次月赛,本次月赛共 \(N\) 题,他计算出了你每道题思考所需的时间 \(t_i\),并且你只要思考出来,他就会帮你打这题的代码,你就可以接着思考下一题。

由于 Leasier 太强了,他的代码交上去一定是会 AC 的,并且由于月赛题实在太水,他可以同时打多道题的代码,现在告诉你每道题你思考的时间 \(t_i\),以及 Leasier 帮你打代码所需的时间 \(s_i\),请你找到一个最优方案使得 AK 的时间尽量早,只有找到了, Leasier神仙才会帮助你。

格式

输入格式

第一行一个整数 \(N\),代表题目数量。

之后 \(N\) 行,每行两个数 \(t_i\) 和 \(s_i\),代表思考时间和敲代码的时间。

输出格式

一行,输出 AK 最少用时。

样例

样例输入1

3
2 5
3 2
2 1

样例输出1

8

说明/提示

样例 1 解释:先思考第一题,再思考第二题,最后思考第三题。

\(1 \le N \le 10^5,1 \le t_i,j_i \le 10^5\)

~~Leasier:这道题谁出的? ~~

【LZR-001】LZOJ 2020 年 6 月月赛 Div.2

未参加
状态
已结束
规则
OI
题目
4
开始于
2020-06-12 18:00
结束于
2020-06-13 14:00
持续时间
20.0 小时
主持人
参赛人数
6