#2888. 「APIO2015」巴邻旁之桥 Palembang Bridges

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 A 和区域 B。
每一块区域沿着河岸都建了恰好 (10^9 + 1) 栋楼,每条岸边的楼都从 0 编号到 10^9 。相邻的每对楼相隔 1 个单位距离,河的宽度也是 1 个单位长度。区域 A 中的 i 号楼恰好与区域 B 中的 i 号楼隔河相对。
城市中有 N 个居民。第 i 个居民的房子在区域 P_i S_i 号建筑上,同时他的办公室坐落在 Q_i 区域的 T_i 号建筑上。有些居民的家在河这边,办公室却在河对岸,这些居民就必须依靠船只才能从家中去往办公室,这种情况让很多人都觉得不方便。为了使居民们可以开车去工作,政府决定建造不超过 K 座横跨河流的大桥。
由于技术上的原因,每一座桥必须刚好连接河的两岸,桥梁必须严格垂直于河流,并且桥与桥之间不能相交。
当政府建造最多 K 座桥之后,设 D_i 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁,使得 D_1 + D_2 + \dots + D_N 最小。

输入格式

输入的第一行包含两个正整数 K N ,分别表示桥的上限数量和居民的数量。
接下来 N 行,每一行包含四个参数: P_i, S_i, Q_i T_i ,表示第 i 个居民的房子在区域 P_i S_i 号建筑上,且他的办公室位于 Q_i 区域的 T_i 号建筑上。

输出格式

输出仅为一行,包含一个整数,表示 D_1 + D_2 + \dots + D_N 的最小值。

样例

样例输入 1

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

样例输出 1

24

样例输入 2

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

样例输出 2

22

数据范围与提示

所有数据都保证: P_i Q_i 为字符 \texttt{A} \texttt{B} 中的一个, 0 \leq S_i, T_i \leq 10^9 ,同一栋建筑内可能有超过 1 间房子或办公室(或二者的组合,即房子或办公室的数量同时大于等于 1 )。

子任务 1 (8 分) K = 1, 1≤N≤1000
子任务 2 (14 分) K = 1, 1≤N≤10^5
子任务 3 (9 分) K = 2, 1≤N≤100
子任务 4 (32 分) K = 2, 1≤N≤1000
子任务 5 (37 分) K=2, 1≤N≤10^5