Không hài lòng với tình trạng sức khỏe kém của đàn bò, Farmer John đăng ký cho chúng tham gia nhiều hoạt động rèn luyện thể chất khác nhau. Cô bò quý Bessie của ông tham gia một lớp chạy bộ, nơi cô được kỳ vọng cuối cùng sẽ chạy một cuộc marathon qua khu trung tâm của thành phố gần trang trại của Farmer John!

Đường chạy marathon gồm \(N\) checkpoint (\(3 \le N \le 500\)) phải được ghé thăm theo thứ tự, trong đó checkpoint 1 là điểm xuất phát và checkpoint \(N\) là đích đến. Bessie lẽ ra phải lần lượt đi qua tất cả các checkpoint này, nhưng vì là một cô bò lười biếng, cô quyết định sẽ bỏ qua nhiều nhất \(K\) checkpoint (\(K < N\)) để rút ngắn tổng quãng đường. Tuy nhiên, cô không thể bỏ qua checkpoint 1 hoặc checkpoint \(N\), vì làm vậy sẽ quá dễ bị phát hiện.

Hãy giúp Bessie tìm quãng đường ngắn nhất mà cô phải chạy nếu được bỏ qua nhiều nhất \(K\) checkpoint.

Vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).

Dữ liệu vào

Dòng đầu tiên chứa các giá trị \(N\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) cách nhau bởi dấu cách, biểu diễn một checkpoint (\(-1000 \le x \le 1000\), \(-1000 \le y \le 1000\)). Các checkpoint được cho theo đúng thứ tự phải ghé thăm. Lưu ý rằng đường chạy có thể tự cắt nhau nhiều lần, và nhiều checkpoint có thể nằm tại cùng một vị trí thực tế. Khi Bessie bỏ qua một checkpoint như vậy, cô chỉ bỏ qua một lần xuất hiện của checkpoint đó, chứ không bỏ qua mọi checkpoint nằm tại cùng vị trí.

Dữ liệu ra

In ra quãng đường ngắn nhất Bessie có thể chạy khi được bỏ qua nhiều nhất \(K\) checkpoint.

Ví dụ

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

4

Nguồn

USACO 2014 December Contest, Silver — Marathon. Tác giả đề: Nick Wu, 2014.

https://usaco.org/index.php?page=viewproblem2&cpid=492