var GET=(function(){function f(s){return new g(s);}function g(s){this._s=s.trim().split("\n");this._y=0;}g.prototype.a=function(f){var s=this._s, y=this._y, r;if(typeof s[y]==="string")s[y]=s[y].split(" ").reverse();r=s[y].pop();if(!s[y].length)this._y++;return f?r:+r;};g.prototype.l=function(f){var s=this._s[this._y++].split(" ");return f?s:s.map(a=>+a);};g.prototype.m=function(n,f){var r=this._s.slice(this._y,this._y+=n).map(a=>a.split(" "));return f?r:r.map(a=>a.map(a=>+a));};g.prototype.r=function(n,f){var r=this._s.slice(this._y,this._y+=n);return f?r:r.map(a=>+a);};return f;})();
var o=GET(require("fs").readFileSync("/dev/stdin","utf8"));
function PriorityQueue(){
  this.heap = [];
}
PriorityQueue.prototype = {
  push : function(x){
    var i = this.heap.length;
    while(i){
      var j = i - 1 >> 1;
      if(x <= this.heap[j])break;
      this.heap[i] = this.heap[j];
      i = j;
    }
    this.heap[i] = x;
  },
  pop : function(){
    var r = this.heap[0];
    var x = this.heap.pop();
    var i = 0;
    var k = this.heap.length >> 1;
    while (i < k) {
      var j = (i << 1) + 1;
      if(this.heap[j] < this.heap[j+1])++j;
      if(x >= this.heap[j])break;
      this.heap[i] = this.heap[j];
      i = j;
    }
    if(this.heap.length)this.heap[i] = x;
    return r;
  },
  size : function(){return this.heap.length;},
  get : function(n){return QuickSelect(n<16?this.heap.slice(0,(1<<n)-1):this.heap.concat(),n);},
};
function QuickSelect(a,k){k=a.length-k;for(var l=0,r=a.length-1,i,j,m,p,t;l<r;){i=l-1;p=a[m=l+r>>1];a[m]=a[j=r];while(1){while(i<j)if(a[++i]>p)break;while(i<j)if(a[--j]<p)break;if(i>=j)break;t=a[i];a[i]=a[j];a[j]=t;}a[r]=a[i];a[i]=p;if(i<k)l=i+1;else if(i>k)r=i-1;else break;}return a[k];}

console.log(main());
function main(){
  var n = o.a();
  var k = o.a();
  var ans = [-1];
  var a = Array(k).fill(0).map(a=>[]);
  var s = 0;
  for(var i = 0; i < n; i++){
    var t = o.l();
    a[t[0]-1].push(t[1]);
    s += t[1];
  }
  ans[n-1] = s;
  if(n === 2)return ans.join("\n");
  var v1 = [], v2 = [], v3 = [];
  var m1 = new PriorityQueue();
  for(i = 0; i < k; i++){
    t = a[i];
    t.sort((a,b)=>a-b);
    var t2 = t.pop() + t.pop();
    v2.push([t2,i]);
    var tl = t.length;
    if(tl)v3.push([t2+t[tl-1],i])
    t2 /= 2;
    v1.push([t2,i,1],[t2,i,2]);
    for(var j = tl; j--;){
      v1.push([t[j],i,0]);
    }
  }
  v1.sort((a,b)=>a[0]<b[0]?1:a[0]>b[0]?-1:a[1]>b[1]?1:a[1]<b[1]?-1:b[2]-a[2]);
  v2.sort((a,b)=>b[0]-a[0]);
  v3.sort((a,b)=>b[0]-a[0]);
  var i1 = 0, i2 = 0, i3 = 0, i0 = 2;
  var k0 = Array(k).fill(0);
  ans[1] = v2[0][0];
  ans[2] = v3[0] ? v3[0][0] : -1;
  s = 0;
  for(i = 3; i < n-1; i++){
    t = 0;
    var f = 1;
    if(i !== i0){
      s += v1[i0-2][0];
      if(v1[i0-2][2] === 2){
        s += v1[i0-1][0];
        i2++;
        for(j = 0; j < a[v1[i0-2][1]].length; j++){
          m1.push(a[v1[i0-2][1]][j]);
        }
        k0[v1[i0-2][1]] = 1;
        f = 0; i0 += 2;
      }else{
        m1.pop();
        i0++;
      }
    }
    if(f){
      if(2 < m1.size()){
        t = m1.get(1) + m1.get(2) + m1.get(3);
      }
      if(m1.size() && v2[i2] && v2[i2][0] + m1.get(1) > t){
        t = v2[i2][0] + m1.get(1);
      }
      for(; i3 < v3.length; i3++){
        if(k0[v3[i3][1]] === 0)break;
      }
      if(i3 !== v3.length && v3[i3][0] > t)t = v3[i3][0];
    }else{
      if(1 < m1.size()){
        t = m1.get(1) + m1.get(2);
      }
      if(v2[i2] && v2[i2][0] > t)t = v2[i2][0];
    }
    ans[i] = t ? s + t : -1;
  }
  return ans.join("\n");
}