#640. [Apio2015]巴邻旁之桥

[Apio2015]巴邻旁之桥

Description

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

每一块区域沿着河岸都建了恰好 1000000001 栋的建筑,每条岸边的建筑都从 0 编号到 1000000000。相邻的每对建筑相隔 1 个单位距离,河的宽度也是 1 个单位长度。区域 A 中的 i 号建筑物恰好与区域 B 中的 i 号建筑物隔河相对。

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

由于技术上的原因,每一座桥必须刚好连接河的两岸,桥梁必须严格垂直于河流,并且桥与桥之间不能相交。当政府建造最多 K 座桥之后,设 Di 表示第 i 个居民此时开车从家里到办公室的最短距离。请帮助政府建造桥梁,使得 D1+D2+⋯+DN 最小。

Format

Input

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

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

Output

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

Samples

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

Limitation

子任务

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

子任务 1 (8 分)

K=1

1≤N≤1000

子任务 2 (14 分)

K=1

1≤N≤100000

子任务 3 (9 分)

K=2

1≤N≤100

子任务 4 (32 分)

K=2

1≤N≤1000

子任务 5 (37 分)

K=2

1≤N≤100000