#include <bits/stdc++.h>
#define NMAX 2005

using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

struct client{
    int h,p;
};

struct cmp{
    bool operator()(const client &a,const client &b){
        return a.h < b.h;
    }
};


client V[NMAX];

int D[NMAX];

int main()
{
    ios :: sync_with_stdio(false);

    int n,C,sol = 0;

    fin >> n >> C;

    for(int i = 1; i <= n; i++){
        fin >> V[i].h >> V[i].p;
    }

    sort(V + 1,V + n + 1,cmp());

    V[0].h = V[1].h;
    V[0].p = 0;

     for(int i = 0; i <= n; i++)
        fout << V[i].h  << "  "<< V[i].p << "\n";


    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= n; j++){
            if(V[j].p >= V[i].p)
                D[j] = max(0, D[j - 1] + V[i].p - (V[j].h - V[j - 1].h) * C);
            else
                D[j] = max(0,D[j - 1] - (V[j].h - V[j - 1].h) * C);

            fout << D[j]  << " ";

            sol = max(sol,D[j]);
        }

        fout << sol << "  " << i << "\n";

    }

    fout << sol;

    return 0;
}