#P18843. [Croatian CPC2022] Dihotomna Dioba

[Croatian CPC2022] Dihotomna Dioba

Dihotomna Dioba

题目描述

Patrick 收到了一张写有谜题的纸条。他决定回家尝试解决这个谜题:把若干个矩形叠成尽可能高的塔。

题目插图

给定 nn 个矩形,每个矩形的两条边长已知。你需要使用全部矩形叠成一座塔:最底层恰好有一个矩形;除最顶层外,每个矩形上方紧接着恰好放置一个矩形,并且上方矩形的宽度必须严格小于下方矩形的宽度。

可以将任意矩形旋转 90∘90^\circ,即交换它的高度和宽度。

求这座塔可以达到的最大总高度。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,每行包含两个整数,表示一个矩形的两条边长。

输出格式

输出一行一个整数,表示按上述规则使用全部矩形所能组成的塔的最大高度。

数据范围

  • 1≤n≤2500001\le n\le250000;
  • 所有边长均为不超过 10910^9 的正整数。

样例 1

输入

3
50000 160000
50000 100000
50000 100000

输出

200000

样例 2

输入

1
5 3

输出

5