#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 25e4 + 5;
const ll LIM = 4e9;
int n, k;
ll x[lim], y[lim];
namespace sub1{
void solve(){
vector<ll>a;
for(int i = 1; i < n; i++){
for(int j = i + 1; j <= n; j++){
a.emplace_back(abs(x[i] - x[j]) + abs(y[i] - y[j]));
}
}
sort(a.begin(), a.end());
for(int i = 0; i < k; i++){
cout << a[i] << "\n";
}
}
}
namespace sub2{
void solve(){
sort(x + 1, x + n + 1);
ll low = 1, high = LIM, d;
while(low <= high){
ll mid = (low + high) >> 1LL;
int cnt = 0;
for(int i = 1, j = 1; i <= n && cnt < k; i++){
while(x[i] - x[j] > mid){
j++;
}
cnt += i - j;
}
if(cnt >= k){
high = (d = mid) - 1;
}
else{
low = mid + 1;
}
}
vector<ll>ans;
for(int i = 1; i <= n; i++){
for(int j = i - 1; j > 0 && x[i] - x[j] < d; j--){
ans.emplace_back(x[i] - x[j]);
}
}
sort(ans.begin(), ans.end());
for(ll& x : ans){
cout << x << "\n";
}
for(int i = ans.size(); i < k; i++){
cout << d << "\n";
}
}
}
namespace sub3456{
struct Node{
int cnt, l, r;
Node(){
this->cnt = 0;
this->l = this->r = -1;
}
};
vector<ll>_x(1, -LLONG_MAX);
vector<Node>st(1, Node());
void copy_left(int id){
if(st[id].l == -1){
st[id].l = st.size();
st.emplace_back(Node());
}
st.emplace_back(st[st[id].l]);
st[id].l = int(st.size()) - 1;
}
void copy_right(int id){
if(st[id].r == -1){
st[id].r = st.size();
st.emplace_back(Node());
return;
}
st.emplace_back(st[st[id].r]);
st[id].r = int(st.size()) - 1;
}
void update(int id, ll l, ll r, ll p){
if(l == r){
st[id].cnt++;
return;
}
ll m = (l + r) >> 1;
if(m < p){
if(st[id].r == -1){
st[id].r = st.size();
st.emplace_back(Node());
}
else{
st.emplace_back(st[st[id].r]);
st[id].r = int(st.size()) - 1;
}
update(st[id].r, m + 1, r, p);
}
else{
if(st[id].l == -1){
st[id].l = st.size();
st.emplace_back(Node());
}
else{
st.emplace_back(st[st[id].l]);
st[id].l = int(st.size()) - 1;
}
update(st[id].l, l, m, p);
}
st[id].cnt++;
}
int get(int id, ll l, ll r, ll u, ll v){
if(l > v || r < u || id == -1){
return 0;
}
if(u <= l && v >= r){
return st[id].cnt;
}
ll m = (l + r) >> 1LL;
return get(st[id].l, l, m, u, v) + get(st[id].r, m + 1, r, u, v);
}
int get(ll X, ll yl, ll yr){
maximize(yl, -LIM);
minimize(yr, LIM);
return get(upper_bound(_x.begin(), _x.end(), X) - _x.begin() - 1, -LIM, LIM, yl, yr);
}
void solve(){
for(int i = 1; i <= n; i++){
x[i] += y[i];
y[i] = x[i] - (y[i] << 1LL);
}
for(int i = 1; i <= n; i++){
_x.emplace_back(x[i]);
}
sort(_x.begin(), _x.end());
_x.resize(unique(_x.begin(), _x.end()) - _x.begin());
{
vector<int>p(n);
iota(p.begin(), p.end(), 1);
sort(p.begin(), p.end(), [&] (int i, int j){
return x[i] < x[j];
});
for(int i = 1; i < _x.size(); i++){
st.emplace_back(Node());
}
int j = 0;
for(int& i : p){
if(x[i] != _x[j]){
j++;
st[j] = st[j - 1];
}
update(j, -LIM, LIM, y[i]);
}
}
ll low = 1, high = LIM, d;
while(low <= high){
ll mid = (low + high) >> 1LL, cnt = 0;
for(int i = 1; i <= n; i++){
cnt += get(x[i] + mid, y[i] - mid, y[i] + mid) - get(x[i] - mid - 1, y[i] - mid, y[i] + mid);
}
if(((cnt - n) >> 1LL) >= k){
high = (d = mid) - 1;
}
else{
low = mid + 1;
}
}
cout << d;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
}
if(n <= 1000){
sub1::solve();
}
else if(count(y + 1, y + n + 1, 0) == n){
sub2::solve();
}
else{
sub3456::solve();
}
}
