#include <bits/stdc++.h>
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define mk make_pair
#define sz(x) (int)(x.size())
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int MAXN = 250010 ;
const ll inf = 1e15+10LL ;
using namespace std ;
int m(int l, int r) { return (r+l)>>1 ; }
pii Y[MAXN] ;
struct Solve
{
ll x[MAXN] , y[MAXN] ;
int seg_index[MAXN] , rt[MAXN] ;
vector<int> e , d ;
vector< pair<ll,int> > mn ;
int create()
{
e.pb(0) ;
d.pb(0) ;
mn.pb(mk(inf,0)) ;
return sz(e)-1 ;
}
int create_and_copy(int pos)
{
e.pb(e[pos]) ;
d.pb(d[pos]) ;
mn.pb(mn[pos]) ;
return sz(e)-1 ;
}
int upd(int pos, int l, int r, int idx, ll val )
{
int newPos = create_and_copy(pos) ;
int aux ;
if(l == r)
{
mn[newPos] = mk(val,l) ;
return newPos ;
}
if( idx <= m(l,r) )
{
aux=upd(e[newPos] , l , m(l,r) , idx, val ) ;
e[newPos] = aux ;
}
else
{
aux = upd(d[newPos] , m(l,r)+1, r, idx, val ) ;
d[newPos] = aux ;
}
mn[newPos] = min(mn[e[newPos]] , mn[d[newPos]]) ;
return newPos ;
}
pair<ll,int> binarySearch(int pos, int l , int r, int R )
{
if( l > R || !pos ) return mk(inf,0) ;
if( r <= R ) return mn[pos] ;
pair<ll,int> al = binarySearch(e[pos] , l , m(l,r) , R ) ;
pair<ll,int> ar = binarySearch(d[pos] , m(l,r)+1, r, R ) ;
return min(al, ar) ;
}
} solve[2] ;
// ----------------------------------
int N , K ;
pii points[MAXN] ;
priority_queue< pair<ll,int> , vector<pair<ll,int> > , greater< pair<ll,int> > > q[2] ;
int main()
{
scanf("%d %d", &N, &K ) ;
lp(i,1,N+1)
{
scanf("%d %d", &points[i].ff, &points[i].ss ) ;
Y[i] = mk(points[i].ss,i) ;
}
sort(Y+1, Y+1+N ) ;
lp(i,1,N+1) points[i].ss = lower_bound(Y+1, Y+1+N, mk(points[i].ss, i ) ) - Y ;
sort(points+1, points+1+N ) ;
lp(i,1,N+1)
{
solve[0].x[i] = points[i].ff ;
solve[0].y[i] = Y[points[i].ss].ff ;
solve[0].seg_index[i] = points[i].ss ;
solve[1].x[i] = -points[N-i+1].ff ;
solve[1].y[i] = Y[points[N-i+1].ss].ff ;
solve[1].seg_index[i] = points[N-i+1].ss ;
}
/*
lp(i,1,N+1) debug("%lld %lld %d\n" , solve[0].x[i] , solve[0].y[i] , solve[0].seg_index[i] ) ;
debug("\n") ;
lp(i,1,N+1) debug("%lld %lld %d\n" , solve[1].x[i] , solve[1].y[i] , solve[1].seg_index[i]) ;
debug("\n") ;
*/
for(int i = 0 ; i < 2 ; i++ )
{
solve[i].rt[0] = solve[i].create() ;
solve[i].rt[1] = solve[i].rt[0] ;
for(int j = 1 ; j <= N ; j++ )
{
ll val = solve[i].x[j]+solve[i].y[j] ;
solve[i].rt[j] = solve[i].upd( solve[i].rt[j] , 1 , N , solve[i].seg_index[j] , -val ) ;
pair<ll,int> p = solve[i].binarySearch( solve[i].rt[j] , 1 , N , solve[i].seg_index[j]-1 ) ;
solve[i].rt[j+1] = solve[i].rt[j] ;
if( p.ss )
{
q[i].push( mk(p.ff+val, j) ) ;
solve[i].rt[j] = solve[i].upd( solve[i].rt[j] , 1 , N , p.ss , inf ) ;
}
}
}
for(int trash = 0 ; trash < K ; trash++ )
{
int idx = 0 ;
if( q[0].empty() || ( !q[1].empty() && q[1].top().ff < q[0].top().ff ) ) idx = 1 ;
printf("%lld\n" , q[idx].top().ff ) ;
int j = q[idx].top().ss ;
q[idx].pop() ;
pair<ll,int> p = solve[idx].binarySearch( solve[idx].rt[j] , 1 , N , solve[idx].seg_index[j]-1 ) ;
if( !p.ss ) continue ;
solve[idx].rt[j] = solve[idx].upd( solve[idx].rt[j] , 1 , N , p.ss , inf ) ;
q[idx].push( mk(p.ff+solve[idx].x[j]+solve[idx].y[j] , j ) ) ;
}
}
