Có ~n~ con bò của người nông dân aihoi đang đứng ở các vị trí riêng biệt có tọa độ lần lượt là ~(x_1, y_1)\dots (x_n, y_n)~ ở trên trang trại hai chiều của anh ta ~(1 ≤ n ≤1000, x_i~ và ~y_i~ đều là các số nguyên dương lẻ có giá trị lớn nhất là ~1.000.000)~. aihoi muốn phân chia mảnh ruộng của anh ta bằng cách dựng một hàng rào bắc - nam dài (có độ dài là vô hạn) bằng phương trình ~x = a~ (~a~ sẽ là một số nguyên chẵn, do đó đảm bảo rằng anh ta không dựng hàng rào đi qua vị trí của bất kì con bò nào). Anh ta cũng muốn dựng một hàng rào đông - tây dài (có độ dài vô hạn) bằng phương trình ~y = b~ (với ~b~ là một số nguyên chẵn). Hai hàng rào giao nhau tại điểm có tọa độ ~(a, b)~ và cùng chia mảnh ruộng thành ~4~ miền. aihoi muốn chọn ~a~ và ~b~ sao cho số bò xuất hiện ở ~4~ miền là cân bằng, mà không có miền nào có quá nhiều con bò. Cho ~M~ là số bò lớn nhất có ở một trong ~4~ miền, aihoi muốn khiến ~M~ nhỏ nhất có thể.

Yêu cầu: Hãy giúp anh ta xác định giá trị nhỏ nhất của ~M~.

Input

• Dòng đầu gồm hai số nguyên dương ~N~;
• ~N~ dòng tiếp theo mỗi dòng chứa vị trí của từng con bò, xác định tọa độ ~x~ và ~y~.

Output

Đưa ra giá trị nhỏ nhất của ~M~ mà aihoi có thể đạt được khi xác định vị trí các hàng rào một cách tối ưu nhất.

Examples

Input

7
7 3
5 5
7 13
3 1
11 7
5 3
9 1

Output

2

Cho một dãy ~N~ số nguyên dương ~A_1, A_2, . . . , A_N~ và một số nguyên ~K~. Một dãy con liên tiếp là một tập hợp các phần tử đứng cạnh nhau.

Yêu cầu: Tìm hai dãy con liên tiếp không giao nhau thỏa mãn:

• Với mỗi dãy con, hai phần tử bất kì trong dãy con chênh lệch giá trị không quá ~K~;
• Tổng số lượng phần tử trong cả hai dãy con là nhiều nhất.

Input

• Dòng đầu chứa hai số nguyên ~N, K \ (1 \le N \le 3 \times 10^5, \ 0 \le K \le 10^9)~;
• Dòng thứ hai chứa N số nguyên ~A_1, A_2, . . . , A_N \ (0 \le A_i \le 10^9)~.

Output

• In ra duy nhất một số là số lượng phần tử nhiều nhất của hai dãy con liên tiếp.

Sample Input 1

5 2
1 3 2 5 4

Sample Output 1

5

Note: Ở ví dụ đầu tiên, ~(1,3,2)~ và ~(5,4)~ là hai dãy con liên tiếp được chọn.

Sample Input 2

5 2
1 3 5 2 4

Sample Output 2

4

Note: Ở ví dụ thứ hai, ~(1,3)~ và ~(2,4)~ là hai dãy con được chọn.

Cho ~n~ số nguyên dương ~a_1, a_2, a_3, ..., a_n~ nhiệm vụ của bạn là với mỗi số ~k \leq i \leq n~ hãy in ra phần tử thứ ~(k + 1)/2~ của dãy ~a_{i - k + 1}, a_{i - k + 2}, ... a_i~ nếu sort nó tăng dần.

Input

• Dòng đầu chứa hai số nguyên dương ~n, k~ - ~k \leq n \leq 200000~
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, ..., a_n~ không vượt quá ~10^9~

Output

• In ra ~n - k + 1~ số là trung vị của các dãy.

Sample Input

8 3
2 4 3 5 8 1 2 1

Sample Output

3 4 5 5 2 1

Cho một dãy số nguyên dương gồm ~N~ phần tử ~A_1, A_2, \dots, A_N~. Với một đoạn con liên tiếp, ta gọi ~F~ của đoạn con đó là độ chênh lệch giữa giá trị lớn nhất và giá trị nhỏ nhất trong đoạn.

Hãy tìm cách chia dãy ban đầu thành các đoạn con liên tiếp sao cho mỗi phần tử thuộc đúng một đoạn con, khi đó ta sẽ thu được một dãy mới gồm các giá trị ~F~ tương ứng của từng đoạn.

Yêu cầu: Hãy tìm cách phân hoạch dãy sao cho độ dài dãy con tăng ngặt dài nhất (LIS) của dãy ~F~ thu được là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \le 2 \times 10^4~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~A_i \le 10^3~).

Output

Gồm một số nguyên duy nhất là độ dài của dãy con tăng dài nhất tìm được.

Scoring

• Subtask ~1~ (~20%~ số điểm): ~N \le 10~.
• Subtask ~2~ (~20%~ số điểm): Dãy số giảm dần và ~A_i = N - i + 1~.
• Subtask ~3~ (~20%~ số điểm): ~N \le 100~.
• Subtask ~4~ (~20%~ số điểm): ~A_i \le 100~.
• Subtask ~5~ (~20%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

8 5 5 1 3 8 7 2 6 

Sample Output 1

3 

Note

Cách chia dãy tối ưu nhất là chia thành ~4~ đoạn: ~[5, 5], [1, 3], [8, 7], [2, 6]~

Các giá trị ~F~ tương ứng là:

• Đoạn 1 ~[5, 5]~: ~F_1 = 5 - 5 = 0~
• Đoạn 2 ~[1, 3]~: ~F_2 = 3 - 1 = 2~
• Đoạn 3 ~[8, 7]~: ~F_3 = 8 - 7 = 1~
• Đoạn 4 ~[2, 6]~: ~F_4 = 6 - 2 = 4~

Dãy ~F~ tạo ra là: ~0, 2, 1, 4~.

LIS của dãy ~F~ là ~0, 1, 4~ hoặc ~0, 2, 4 \rightarrow~ độ dài ~3~.

Một dãy các số ~a_1,a_2,...,a_n~ được gọi là dãy kẹp nếu ~a_1 \le a_i \le a_n~, ~\forall i \in [1,n]~. Nếu ~n \le 2~ thì là dãy kẹp nếu ~a_1 \le a_n~.

Các ví dụ về dãy kẹp: ~[1],[1,1],[3,4,3,4],[1,3,2,4]~. Các ví dụ về dãy không phải dãy kẹp: ~[],[2,3,1],[2,1,4,3]~.

Cho mảng ~a = [a_1,a_2,...,a_n]~, hãy đếm xem có bao nhiêu mảng con liên tiếp của ~a~ là dãy kẹp.

Input

• Dòng đầu chứa số nguyên dương ~𝑛~ ~(𝑛 ≤ 10^6)~.
• Dòng sau chứa dãy ~a~ ~(1 \le a_i \le 10^9)~.

Subtask

• Subtask ~1~ ~(10\%)~ : ~n \le 300~
• Subtask ~2~ ~(20\%)~ : ~1 \le n \le 10^5, 1 \le a_i \le 2~
• Subtask ~3~ ~(20\%)~ : ~n \le 5000~
• Subtask ~4~ ~(30\%)~ : ~n \le 10^5~
• Subtask ~5~ ~(20\%)~: Không giới hạn gì thêm

Output

• In ra một số là kết quả bài toán.

Sample Input 1

5
1 2 4 3 5

Sample Output 1

11

Sample Input 1

8
2 1 6 3 6 7 8 5

Sample Output 1

18

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