The CODEleones

#include <fstream>
#include <iomanip>

using namespace std;

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

int n, k;

struct data {
    int h;
    int c;
}v[1005];

int d1[1005], d2[1005], d[1005];

inline int modul(int x) {
    return (x > 0 ? x : -x);
}

bool verif(int H) {

    for (int i = 0; i <= 1000; i++)
        d1[i] = d2[i] = 0;

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

        int front = 1, back = 0;

        for (int j = 0; j < 1000; j++) {

            while (front <= back && d1[j] <= d1[d[back]])
                back--;

            d[++back] = j;

            if (j - d[front] == 2 * H + 1)
                front++;

            int x = j - H;

            if (x > 0)
                d2[x] = d1[d[front]] + modul(v[i].h - j + H) * v[i].c;

        }

        for (int j = 1000 - H; j <= 1000; j++) {

            if (j - d[front] == 2 * H + 1)
                front++;

            d2[j] = d1[d[front]] + modul(v[i].h - j) * v[i].c;

        }

        for (int j = 0; j <= 100; j++) {
            d1[j] = d2[j];
            d2[j] = 0;
        }

    }
    if (d1[H] <= k)
        return 1;
    return 0;

}

int main() {

    fin >> n >> k;

    for (int i = 1; i <= n; i++)
        fin >> v[i].h >> v[i].c;

    int st = 0, dr = 1000;

    while (st <= dr) {

        int mid = (st + dr) / 2;

        if (verif(mid))
            dr = mid - 1;
        else
            st = mid + 1;

    }

    fout << st << "\n";

    return 0;
}