Không hài lòng với sức khỏe của bò, Farmer John đăng ký cho chúng nhiều hoạt động thể dục. Cô bò quý Bessie học chạy và cuối cùng sẽ chạy marathon qua trung tâm thành phố gần trang trại!

Đường chạy có $N$ điểm kiểm tra, $3 \leq N \leq 500$, phải ghé theo thứ tự. Điểm 1 là xuất phát, điểm $N$ là đích. Bessie phải ghé tất cả nhưng vì lười nên quyết định bỏ qua tối đa $K$ điểm, với $K<N$, để rút ngắn đường. Không được bỏ điểm 1 hoặc $N$ vì sẽ quá dễ bị phát hiện.

Tìm khoảng cách ít nhất cần chạy khi bỏ qua tối đa $K$ điểm.

Phố ở trung tâm tạo thành lưới, nên khoảng cách giữa $(x1, y1)$ và $(x2, y2)$ là $|x1-x2| + |y1-y2|$.

Dữ liệu vào

Dòng đầu cho $N$ và $K$.

$N$ dòng tiếp theo chứa hai số nguyên $x$ và $y$ cách nhau bởi dấu cách, tọa độ một điểm ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). Điểm được cho theo thứ tự phải ghé. Đường có thể tự cắt nhiều lần và nhiều điểm có thể cùng vị trí. Bỏ qua một điểm như vậy chỉ bỏ một lần xuất hiện, không bỏ tất cả điểm tại cùng vị trí.

Dữ liệu ra

In khoảng cách ít nhất khi bỏ qua tối đa $K$ điểm. Trong ví dụ, bỏ $(8, 3)$ và $(10, -5)$ cho tổng khoảng cách nhỏ nhất là 4.

Ví dụ

Dữ liệu vào 1

5 2
0 0
8 3
1 1
10 -5
2 2

Dữ liệu ra 1

4

Tác giả: Nick Wu, 2014