#5001. [APIO2015] 八邻旁之桥

[APIO2015] 八邻旁之桥

题目描述

一条东西走向的穆西河将巴邻旁市一分为二,分割成了区域 AA 和区域 BB

每一块区域沿着河岸都建了恰好 10000000011000000001 栋的建筑,每条岸边的建筑都从 00 编号到 10000000001000000000。相邻的每对建筑相隔 11 个单位距离,河的宽度也是 11 个单位长度。区域 AA 中的 ii 号建筑物恰好与区域 BB 中的 ii 号建筑物隔河相对。

城市中有 NN 个居民。第 ii 个居民的房子在区域 PiP_iSiS_i 号建筑上,同时他的办公室坐落在 QiQ_i 区域的 TiT_i 号建筑上。一个居民的房子和办公室可能分布在河的两岸,这样他就必须要搭乘船只才能从家中去往办公室,这种情况让很多人都觉得不方便。为了使居民们可以开车去工作,政府决定建造不超过 KK 座横跨河流的大桥。

由于技术上的原因,每一座桥必须刚好连接河的两岸,桥梁必须严格垂直于河流,并且桥与桥之间不能相交。

当政府建造最多 KK 座桥之后,设 DiD_i 表示第 ii 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁,使得 D1+D2++DND_1 + D_2 + \cdots + D_N 最小。

输入格式

输入的第一行包含两个正整数 KKNN,分别表示桥的上限数量和居民的数量。

接下来 NN 行,每一行包含四个参数:Pi,Si,QiP_i, S_i, Q_iTiT_i,表示第 ii 个居民的房子在区域 PiP_iSiS_i 号建筑上,且他的办公室位于 QiQ_i 区域的 TiT_i 号建筑上。

输出格式

输出仅为一行,包含一个整数,表示 D1+D2++DND_1 + D_2 + \cdots + D_N 的最小值。

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

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

提示

【数据范围】

所有数据都保证:PiP_iQiQ_i 为字符 “A” 和 “B” 中的一个, 0Si,Ti10000000000 \leq S_i, T_i \leq 1000000000,同一栋建筑内可能有超过 11 间房子或办公室(或二者的组合,即房子或办公室的数量同时大于等于 11)。

子任务 1 (8 分)K=1K = 1

1N10001 \leq N \leq 1000

子任务 2 (14 分)K=1K = 1

1N1000001 \leq N \leq 100000

子任务 3 (9 分)K=2K = 2

1N1001 \leq N \leq 100

子任务 4 (32 分)K=2K = 2

1N10001 \leq N \leq 1000

子任务 5 (37 分)K=2K = 2

1N1000001 \leq N \leq 100000