UOJ Logo

NOI.AC

1S 512MB

#1579. 覆盖

Statistics

题目描述

$100000 \* 100000$的网格平面上有$n$个正方形 你现在可以按上下左右任意移动这些正方形,但每移动一格就需要$1$的代价 现在你要让平面上存在某一个格子被所有正方形都覆盖 求最小代价使其满足条件

输入格式

第一行一个数$n$,表示正方形个数 下面$n$行每行四个数$a,b,c,d$,表示正方形左下角是$(a,b)$,右上角是$(c,d)$

输出格式

一个数,表示最小代价

样例数据

input

2
2 2 3 3
4 4 5 5

output

2

数据规模与约定

对于20%的数据,$n=2$ 对于另外30%的数据, $n \le 5 $且每个正方形面积都为1 对于另外30%的数据,$n \le 1000$ 对于另外20%的数据,$n \le 100000$