始皇修路

题目背景

昔者秦王并吞六国，混一寰宇，书同文，车同轨。思欲通达四海，固江山之基，乃命内史腾监造驰道。

大秦版图，纵横万里，其间沃野、崇山、大泽交错。王命：择关中、齐鲁、燕赵、荆楚、吴越等要冲之地，共计 K 处，定为“枢纽”。

承命大臣需于大地网格之上，筑路以联此 K 处。然国库虽丰，亦不欲徒耗民力。凡筑路者，必循经纬之线，或南北，或东西。

每历一格，耗金若干。且山川险易不同，某些地域有巨石险滩，不可逾越；某些地域则已有前朝废弃古道，修复之耗极微。

内史腾欲求一策，使此 K 处枢纽尽皆连通，且总耗金最少。若不能连通，则大秦威严受损，必究其责。

尔等工部后进，能以此算筹之术，定此锦绣山河之枢纽乎？

题目描述

在大秦帝国的广袤国土上，你需要设计一个最优的交通网络。国土被抽象为一个巨大的坐标平面。

给定 K 个必须连通的枢纽城市，每个城市的坐标为 (x_i, y_i)。

道路只能沿水平或垂直方向修建（曼哈顿距离）。由于地理环境的差异，在某些特定的网格区域（矩形区域）修建道路的单位长度成本不同。

你的目标是找到一种方案，使得所有 K 个城市连通，且总修建成本最低。

输入格式

第一行包含一个整数 K，表示枢纽城市的数量。

接下来的 K 行，每行包含两个整数 x_i, y_i，表示枢纽城市的坐标。

下一行包含一个整数 M，表示具有特殊成本的矩形区域数量。

接下来的 M 行，每行包含 x_{1}, y_{1}, x_{2}, y_{2}, c，表示在左下角 (x_1, y_1) 到右上角 (x_2, y_2) 的矩形区域内（含边界），单位道路修建成本为 c。

默认的全球单位道路成本为 $C_{default}$（在输入中给定）。

输出格式

一行一个整数$P$，代表最小的修建成本

输入输出样例 #1

输入 #1

3

1 1

2 2

3 3

0

1

输出 #1

4

说明/提示

样例$1$说明：

$3$个枢纽在 $$ (1,1), (2,2), (3,3) $$ ，无特殊区域，默认单位成本为 1。

最优方案是连接 $$ (1,1) - (2,1) - (2,2) - (3,2) - (3,3) $$ ，总长度 4

保证$$0 \le P \le 2^{128}$$

重合特殊成本区域的成本以更小的计