#P18843. [Croatian CPC2022] Dihotomna Dioba
[Croatian CPC2022] Dihotomna Dioba
Dihotomna Dioba
题目描述
Patrick 收到了一张写有谜题的纸条。他决定回家尝试解决这个谜题:把若干个矩形叠成尽可能高的塔。

给定 个矩形,每个矩形的两条边长已知。你需要使用全部矩形叠成一座塔:最底层恰好有一个矩形;除最顶层外,每个矩形上方紧接着恰好放置一个矩形,并且上方矩形的宽度必须严格小于下方矩形的宽度。
可以将任意矩形旋转 ,即交换它的高度和宽度。
求这座塔可以达到的最大总高度。
输入格式
第一行包含一个整数 。
接下来 行,每行包含两个整数,表示一个矩形的两条边长。
输出格式
输出一行一个整数,表示按上述规则使用全部矩形所能组成的塔的最大高度。
数据范围
- ;
- 所有边长均为不超过 的正整数。
样例 1
输入
3
50000 160000
50000 100000
50000 100000
输出
200000
样例 2
输入
1
5 3
输出
5