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

2163: 起重机利润最大化

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

题目描述

小明设计并建造了一辆可搭载起重机的铁路货车。
该货车从 1 号城市出发，沿途经过 2,...,N-1 号城市到达 N 号城市，途中不可改变行进方向，且只能进行一次旅程。
每个城市都有一个起重机类型清单，小明可以在其中购买和出售起重机，价格因城市而异。
当货车到达某个城市时，他可以购买一台起重机，然后在后续拥有相同类型起重机的城市中出售，以获取利润。
每次只能运输一台起重机，但可以多次重复这个动作。
此外，小明也可以在城市之间旅行而不携带起重机。
在旅程开始时，小明有足够的预算，在任何城市都可以购买起重机。
请求出在整个旅程中获得的最大利润。

输入格式

第一行为正整数 N，1≤N≤100000。
接下来 N 部分，每部分第一行为正整数 M，表示这个城市的起重器类别数。
接下来 M 行，每行两个这个部分是关于 I 和 P，分别表示类别和价格。
在每个城市中，只能购买或者售出当前城市具备的类别。

输出格式

输出一个整数表示答案。

输入样例 复制 

样例一：
5
1
1 3
1
1 2
1
1 3
1
1 5
1
1 1

样例二：
4
2
1 2
2 1
2
1 3
2 5
1
1 4
1
2 6

输出样例 复制 

样例一：
3

样例二：
5

数据范围与提示

来源：2022 CTU Open