4082. 魔法传送阵

【题目描述】

      一条东西走向的穆西河将巴邻旁市一分为二，分割成了区域 A 和区域B。每一块区域沿着河岸都建了恰好 1000000001 栋的建筑，每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离，河的宽度也是 1 个单位长度。区域A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。

          城市中有 N 个居民。第 i 个居民的房子在区域 Pi 的 Si 号建筑上，同时他的办公室坐落在Qi 区域的 Ti 号建筑上。一个居民的房子和办公室可能分布在河的两岸，这样他就必须要搭乘船只才能从家中去往办公室，这种情况让很多人都觉得不方便，所以他们决定不乘船。魔法师公会决定建造不超过K对横跨河流的传送阵。

由于技术上的原因，每一对传送阵必须刚好连接河的对岸(即 $A_i \rightarrow B_i$)，并且为了避免任意两对传送阵间出现互相干扰，任意两对传送阵之间不能相交。

          当魔法师公会建造最多K对传送阵之后，设 Di 表示第i 个居民此时从家里到办公室的最短距离。请帮助魔法师公会建造传送阵，使得D1+D2+⋯+DN 最小。

【输入格式】

输入的第一行包含两个正整数 K 和 N，分别表示传送阵的上限数量和居民的数量。

接下来 N 行，每一行包含四个参数：Pi,Si,Qi 和 Ti，表示第 i 个居民的房子在区域 Pi 的 Si 号建筑上，且他的办公室位于Qi 区域的Ti 号建筑上。

【输出格式】

输出仅为一行，包含一个整数，表示D1+D2+⋯+DN 的最小值。

【样例输入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

【样例说明】

在此键入。

大样例

【数据规模与约定】

所有数据都保证：Pi 和 Qi 为字符 “A” 和 “B” 中的一个，0≤Si,Ti≤1000000000，同一栋建筑内可能有超过 1间房子或办公室（或二者的组合，即房子或办公室的数量同时大于等于 1）。

对于8%的数据 K=1  1≤N≤1000

对于14%的数据 K=1  1≤N≤100000

对于9%的数据  K=2  1≤N≤100

对于32%的数据 K=2  1≤N≤1000

对于37%的数据 K=2  1≤N≤100000

【来源】

APIO2015。