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