Cho một số nguyên dương ~N~. Hãy đếm xem có bao nhiêu bộ số nguyên dương ~(a, b, c)~ sao cho ~a \times b \times c = N~ và ~a \leq b \leq c~.

Input

• Gồm một số nguyên dương ~N~ duy nhất.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~40\%~ số điểm): ~N \leq 100~.
• Subtask 2 (~60\%~ số điểm): ~N \leq 10^7~.

Sample Test

Input:

8

Output:

3

Note:

• Có ba bộ số là ~(1, 1, 8)~, ~(1, 2, 4)~, ~(2, 2, 2)~.

Thành phố XYZ bị một dòng sông chia cắt thành hai vùng là A và B. Mỗi vùng bao gồm dòng sông và một dãy toà nhà chạy dọc theo bờ sông, được đánh số từ ~0~ đến ~10^9~. Khoảng cách giữa hai toà nhà kề nhau là ~1~ đơn vị, và bề rộng dòng sông cũng bằng ~1~ đơn vị. Toà nhà ~i~ ở vùng A luôn đối diện với toà nhà ~i~ ở vùng B.

Có ~N~ công dân sinh sống và làm việc trong thành phố. Công dân ~i~ sống ở vùng ~P_i~ tại toà nhà ~S_i~ và làm việc ở vùng ~Q_i~ tại toà nhà ~T_i~. Hiện tại họ phải qua sông bằng thuyền, nên chính phủ quyết định xây dựng ~K~ cây cầu để người dân có thể đi lại bằng xe.

Mỗi cây cầu phải được đặt giữa đúng hai toà nhà đối diện nhau và 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 ~D_i~ là khoảng cách nhỏ nhất mà công dân ~i~ phải di chuyển từ nhà đến nơi làm việc sau khi xây dựng ~K~ cây cầu.

Yêu cầu: Tìm phương án xây dựng ~K~ cây cầu sao cho tổng ~D_1 + D_2 + \dots + D_N~ là nhỏ nhất.

Input

• Dòng đầu chứa hai số nguyên ~K~ và ~N~ (~K \le 2~; ~1 \le N \le 10^5~).
• Mỗi trong ~N~ dòng tiếp theo chứa bốn giá trị ~P_i, S_i, Q_i, T_i~:
  • ~P_i \in \{A, B\}~, ~S_i~ là toà nhà (~0 \le S_i \le 10^9~).
  • ~Q_i \in \{A, B\}~, ~T_i~ là toà nhà (~0 \le T_i \le 10^9~).
• Có thể có nhiều công dân có nhà hoặc nơi làm việc trùng cùng một toà nhà.

Output

• In ra một số nguyên duy nhất — tổng khoảng cách nhỏ nhất.

Subtasks

• 25%: ~K = 1~, ~1 \le N \le 10^3~
• 25%: ~K = 1~, ~1 \le N \le 10^5~
• 25%: ~K = 2~, ~1 \le N \le 10^3~
• 25%: ~K = 2~, ~1 \le N \le 10^5~

Sample Test

Input 1

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

Output 1

24

Input 2

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

Output 2

22