New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2181: 安装零件

内存限制：512 MB 时间限制：3 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：1
提交提交记录统计

题目描述

给定 N 种零件，第 i 种零件数量为 fi，安装时间为 ti。
机器人将上述所有零件安装到电路板上：
每次可以安装一个类型 i 的零件，花费时间为ti；
每次也可以同时安装类型 i 和类型 j 的零件各一个，花费时间为max(ti,tj)。
计算机器人最小花费时间。

输入格式

第一行为正整数 N，N≤1000。
接下来 N 行，每行两个整数 fi,ti，1≤fi≤10000,1≤ti≤109。

输出格式

输出一个整数表示答案。

输入样例 复制 

样例1：
3
2 7
2 1
3 10

样例2：
3
2 10
2 11
2 12

样例3：
4
2 11
7 10
3 5
1 1

输出样例 复制 

样例1：
31

样例2：
35

样例3：
72

数据范围与提示

来源：2023 NCPC