圣彼得堡动物园的北极熊 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
注意
在两个给定样本中可以获得的形状是:
在第一个示例中,您需要删除任何线段,因为这两个线段在一起不会形成单个连接的形状。
在第二个示例中,初始片段形成一个循环,有四种方法可以打破循环:完全删除第一、第二或第四片段或删除第三片段的中间。最后一种方式如图所示。