#2373. 午餐

午餐

午餐

题目描述

午餐 上午的训练结束了,THU ACM 小组集体去吃午餐,他们一行N 人来到了著名的十食堂。 这里有两个打饭的窗口,每个窗口同一时刻只能给一个人打饭。由于每个人的口味(以及胃 口)不同,所以他们要吃的菜各有不同,打饭所要花费的时间是因人而异的。另外每个人吃饭 的速度也不尽相同,所以吃饭花费的时间也是可能有所不同的。 THU ACM 小组的吃饭计划是这样的:先把所有的人分成两队,并安排好每队中各人的 排列顺序,然后一号队伍到一号窗口去排队打饭,二号队伍到二号窗口去排队打饭。每个人 打完饭后立刻开始吃,所有人都吃完饭后立刻集合去六教地下室进行下午的训练。 现在给定了每个人的打饭时间和吃饭时间,要求安排一种最佳的分队和排队方案使得 所有人都吃完饭的时间尽量早。 假设THU ACM 小组在时刻0 到达十食堂,而且食堂里面没有其他吃饭的同学(只有打 饭的师傅)。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的,而且 每个人打饭的时间是和窗口无关的,打完饭之后立刻就开始吃饭,中间没有延迟。 现在给定N 个人各自的打饭时间和吃饭时间,要求输出最佳方案下所有人吃完饭的时 刻。 输入 第一行一个整数N,代表总共有N 个人。 以下N 行,每行两个整数 Ai,Bi。依次代表第i 个人的打饭时间和吃饭时间。 输出 一个整数T,代表所有人吃完饭的最早时刻。 约定 所有输入数据均为不超过200 的正整数。

样例输入 5 2 2 7 7 1 3 6 4 8 5 样例输出 17 样例说明 方案如下: 窗口1: 窗口2: 7 7 1 3 6 4 8 5 2 2

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5
2 2
7 7
1 3
6 4
8 5
17