2888 「APIO2015」巴邻旁之桥

一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 A 和区域 B。

每一块区域沿着河岸都建了恰好 $1,000,000,001$ 栋楼，每条岸边的楼都从 $0$ 编号到 $1,000,000,000$。相邻的每对楼相隔 $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 可能的一组最优方案，粉色的区域表示一座桥。

下面是样例 2 的一组可能的最优方案。

所有数据都保证：$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$