Thành phố Palembang bị dòng sông Musi chia cắt thành hai phần. Ta sẽ gọi chúng là vùng A và vùng B. Mỗi vùng bao gồm đúng 1,000,000,001 toà nhà chạy dọc theo bờ sông được đánh số từ 0 đến 10^9. Khoảng cách giữa mỗi cặp toà nhà liền kề là 1 đơn vị khoảng cách. Bề rộng của dòng sông cũng là 1 đơn vị khoảng cách. Toà nhà i ở vùng A là đối diện với toà nhà i ở vùng B.

Có N công dân sống và làm việc trong thành phố. Nhà của công dân i trong vùng Pi ở toà nhà Si, trong khi đó trụ sở cơ quan làm việc của công dân này lại ở vùng Qi toà nhà Ti. Khi đi từ nhà đến trụ sở làm việc công dân phải vượt qua sông bằng thuyền. Điều đó là hết sức bất tiện cho người dân, vì thế chính phủ quyết định xây dựng K cây cầu qua sông để các công dân có thể lái xe đi làm. Mỗi cây cầu phải được xây dựng giữa đúng hai toà nhà đối diện ở hai vùng. Các cây cầu phải vuông góc với dòng sông. Các cây cầu không được chồng lên nhau.

Ký hiệu Di là khoảng cách nhỏ nhất mà công dân i phải lái xe từ nhà của mình đến trụ sở làm việc sau khi chính phủ xây dựng xong K cây cầu. Hãy giúp chính phủ tìm phương án xây dựng K cây cầu sao cho tổng D1 + D2 + ... + DN là nhỏ nhất.

Input:

• Dòng đầu tiên chứa hai số nguyên K và N.

• Mỗi dòng trong N dòng tiếp theo chứa 4 thông số Pi, Si, Qi và Ti.

Output :

Một dòng duy nhất chứa tổng khoảng cách nhỏ nhất

Sample input 1:

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

Sample output 1:

24

Sample input 2:

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

Sample output 2:

22

Giới hạn:

0 ≤ Si, Ti ≤ 10^9. Có thể có nhiều hơn 1 căn hộ hoặc trụ sở cơ quan (hoặc tổ hợp cả hai) thuộc cùng một toà nhà.
Subtask 1 : K = 1 ; 1 ≤ N ≤ 1000;
Subtask 2 :  K = 1 ;  1 ≤ N ≤ 100000;
Subtask 3 : K = 2 ; 1 ≤ N ≤ 100;
Subtask 4 :  K = 2 ;  1 ≤ N ≤ 1000; 
Subtask 5 : K = 2 ; 1 ≤ N ≤ 100000;