Cho \(n\) điểm phân biệt có tọa độ nguyên trên mặt phẳng. Dữ liệu bảo đảm tồn tại \(k\) đường thẳng song song với nhau, cùng song song với trục \(Ox\) hoặc cùng song song với trục \(Oy\), sao cho mọi điểm đã cho đều nằm trên các đường thẳng này.

Bạn cần dùng các đoạn thẳng ngang hoặc dọc có đầu mút nguyên để nối tất cả các điểm thành một thành phần liên thông. Chi phí của một cấu hình là tổng độ dài Manhattan của các đoạn thẳng được sử dụng. Hãy tìm một cấu hình hợp lệ có chi phí càng nhỏ càng tốt.

Hai điểm được xem là liên thông nếu có thể đi từ điểm này đến điểm kia dọc theo hợp của các đoạn thẳng đã chọn.

Dữ liệu vào

Mỗi tệp dữ liệu có định dạng:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i\) và \(y_i\), là tọa độ của một điểm.

Trong bộ dữ liệu hiện tại, \(1 \le n \le 1000\), \(1 \le k \le 5\) và \(0 \le x_i, y_i \le 10^9\).

Đây là bài toán dạng output-only. Tải bộ dữ liệu đầu vào hiện tại. Với mỗi tệp inputs/<tên>.in, hãy tạo tệp kết quả tương ứng tại outputs/<tên>.out và nén thư mục outputs thành tệp ZIP để nộp.

Dữ liệu ra

Mỗi tệp kết quả có định dạng:

• Dòng đầu tiên chứa số nguyên \(C\) — tổng độ dài của các đoạn thẳng.
• Dòng thứ hai chứa số nguyên \(m\) — số đoạn thẳng được sử dụng.
• \(m\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), mô tả đoạn thẳng nối \((x_1,y_1)\) với \((x_2,y_2)\).

Cấu hình phải thỏa mãn:

• Mỗi đoạn thẳng phải nằm ngang hoặc thẳng đứng và có hai đầu mút nguyên.
• \(C\) phải đúng bằng tổng độ dài Manhattan của \(m\) đoạn thẳng.
• Mọi điểm đầu vào phải thuộc hợp các đoạn thẳng và tất cả các điểm phải liên thông với nhau.
• Hai đoạn thẳng khác nhau chỉ được có nhiều nhất một điểm chung. Nếu có điểm chung, điểm đó phải là đầu mút của cả hai đoạn. Vì vậy, các đoạn không được chồng lấn, cắt nhau ở phần trong hoặc tạo thành nút giao chữ T.

Chấm điểm

Với mỗi tệp dữ liệu, gọi \(J\) là chi phí của đáp án Ban giám khảo và \(C\) là chi phí của kết quả hợp lệ của bạn.

• Nếu \(C \le J\), bạn nhận toàn bộ điểm của tệp đó.
• Nếu \(J < C \le 2J\), đặt \(\Delta = \dfrac{C-J}{J}\); bạn nhận tỉ lệ \((1-\Delta)^2\) điểm của tệp đó.
• Nếu \(C > 2J\) hoặc kết quả không hợp lệ, bạn không nhận điểm của tệp đó.

Bộ dữ liệu gồm \(20\) tệp có trọng số bằng nhau:

• Nhóm 1 (\(15\%\)): \(n \le 7\).
• Nhóm 2 (\(10\%\)): \(n \le 50\).
• Nhóm 3 (\(15\%\)): \(k=2\).
• Nhóm 4 (\(15\%\)): \(k \in \{3,4\}\).
• Nhóm 5 (\(45\%\)): \(k=5\).

Ví dụ

3 3
0 1
1 0
2 2

4
4
0 1 1 1
1 0 1 1
1 1 1 2
1 2 2 2