← 返回题目列表

Codeforces · 471/E

E. MUH 和很多很多的段

中文机器翻译题面 查看原题

圣彼得堡动物园的北极熊 Menshykov 和 Uslada 以及基辅动物园的大象 Horace 决定画一些画。当他们试图创作他们的第一个杰作时,他们在一张纸上画了草稿。草稿由 n 段组成。每个部分要么是水平的,要么是垂直的。现在小伙伴们想通过删除一些片段或部分片段来简化草稿,使最终的杰作满足三个条件:

1. 霍勒斯希望能够一笔画出整个图画:将画笔放在纸上,直到图画准备好才将其取下。画笔可以在同一个地方多次绘制。这就是为什么所有剩余的部分必须形成一个连接的形状。
2. Menshykov 希望生成的形状简单。他将简单形状定义为不包含任何循环的形状。
3. 最初,草稿上的所有线段都有整数起点和终点坐标。 Uslada 不喜欢真实的坐标,她希望在所有更改后满足此条件。

由于草稿的其他部分已经很漂亮了,朋友们决定删除草稿中剩余片段长度之和尽可能大的部分。您的任务是计算删除所有额外线段后剩余长度的最大总和。

输入

输入的第一行包含整数 n (1 ≤ n ≤ 2·105) — 草稿上的段数。接下来的 n 行每行包含四个整数:x1, y1, x2, y2 ( - 109 ≤ x1 ≤ x2 ≤ 109; - 109 ≤ y1 ≤ y2 ≤ 109) — 线段的两个起点和两个终点坐标。所有节段都是非退化的,并且要么是严格水平的,要么是严格垂直的。

没有两个水平线段共享公共点。没有两个垂直线段有共同点。

输出

打印单个整数 — 剩余段的最大长度总和。

示例

输入 #1

2
0 0 0 1
1 0 1 1

输出 #1

1

输入 #2

4
0 0 1 0
0 0 0 1
1 -1 1 2
0 1 1 1

输出 #2

5

注意

在两个给定样本中可以获得的形状是:

在第一个示例中,您需要删除任何线段,因为这两个线段在一起不会形成单个连接的形状。

在第二个示例中,初始片段形成一个循环,有四种方法可以打破循环:完全删除第一、第二或第四片段或删除第三片段的中间。最后一种方式如图所示。