/* 0257: Lazy Cows */
/* Hal Burch */
/*
TASK: lazy
LANG: C
*/
/*
Mon Apr 25 21:09:58 EDT 2005
Mon Apr 25 21:47:31 EDT 2005
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define INFTY 2000000001

#define NAME "lazy"

#define MAXC 2500
#define MAXB 2500

int cow1[MAXC];
int ncow1;

int cow2[MAXC];
int ncow2;

int nbarn;

typedef struct {
    int topmin;
    int botmin;
    int bothmin;
    int spanmin;
} min_t;

min_t min[MAXB+2];

int
int_comp(const void *pa, const void *pb) {
    return *(int*)pa - *(int*)pb;
}

int
main(int argc, char **argv) {
    FILE *fin, *fout;
    int ncow;
    int x, y;
    int lv;
    int i1, i2;
    int c1, c2;
    int l1, l2;
    int t;

    if (argc > 1) {
        fin = fopen(argv[1], "r");
        fout = stdout;
    } else {
        fin = fopen(NAME ".in", "r");
        fout = fopen(NAME ".out", "w");
    }
    assert(fin);
    assert(fout);
    fscanf (fin, "%d %d %d", &ncow, &nbarn, &lv); /* discard lv */
    for (lv = 0; lv < ncow; lv++) {
        fscanf (fin, "%d %d", &x, &y);
        if (x == 1) cow1[ncow1++] = y;
        else {
            assert(x == 2);
            cow2[ncow2++] = y;
        }
    }
    fclose(fin);

    qsort(cow1, ncow1, sizeof(*cow1), int_comp);
    qsort(cow2, ncow2, sizeof(*cow2), int_comp);

    for (lv = 0; lv <= nbarn; lv++)
        min[lv].topmin = min[lv].botmin = min[lv].bothmin = 
        min[lv].spanmin = INFTY;

    min[0].topmin = min[0].botmin = min[0].bothmin = min[0].spanmin = 0;

    i1 = 0;
    i2 = 0;

    l1 = c1-1;
    l2 = c2-1;
    
    while (i1 < ncow1 || i2 < ncow2) {
        if (i1 < ncow1) c1 = cow1[i1];
        else c1 = -1;
        if (i2 < ncow2) c2 = cow2[i2];
        else c2 = -1;

#if 0
        fprintf (stderr, "%d/%d:\n", c1, c2);
        for (lv = 1; lv <= nbarn; lv++) {
            fprintf (stderr, "     %d: top %d, bot %d, both %d, span %d\n", lv, min[lv].topmin, min[lv].botmin, min[lv].bothmin, min[lv].spanmin);
        }
#endif

        if (i1 == 0 && i2 == 0) {
            if (c1 == c2) {
                min[1].spanmin = 2;
                min[2].bothmin = 2;
                l1 = l2 = c1;
                i1++; i2++;
            } else if (c1 == -1 || c2 < c1) {
                min[1].spanmin = 2;
                min[1].botmin = 1;
                l1 = l2 = c2;
                i2++;
            } else {
                assert(c2 == -1 || c1 < c2);
                min[1].spanmin = 2;
                min[1].topmin = 1;
                l1 = l2 = c1;
                i1++;
            }
            min[0].spanmin = min[0].bothmin = min[0].botmin = min[0].topmin = INFTY;
            continue;
        }

        if (c1 == -1) { /* Only bottom cows left */
            for (lv = nbarn; lv > 0; lv--) {
                /* No way to cover with just top barn */
                min[lv].topmin = INFTY;

                /* Extend top barn */
                min[lv].botmin += c2 - l2;

                t = l1;
                if (t < l2) t = l2;
                /* End top barn */
                t = min[lv].bothmin + (c2 - t);
                if (min[lv].botmin > t) min[lv].botmin = t;

                t = l1;
                if (t < l2) t = l2;

                /* Extend both barns */
                min[lv].bothmin += 2*(c2 - t);

                /* Extend spanning barn */
                min[lv].spanmin += 2*(c2 - t);

                /* Start new barn */
                t = min[lv-1].topmin;
                if (min[lv-1].botmin < t) t = min[lv-1].botmin;
                if (min[lv-1].bothmin < t) t = min[lv-1].bothmin;
                if (min[lv-1].spanmin < t) t = min[lv-1].spanmin;
                if (min[lv].botmin > t+1) min[lv].botmin = t+1;

                /* Would never want to continue top barn */
                /* Never want to start both barns now */
            }
            l2 = c2;
            ++i2;
        } else if (c2 == -1) { /* Only top cows left */
            for (lv = nbarn; lv > 0; lv--) {
                /* No way to cover with just top barn */
                min[lv].botmin = INFTY;

                /* Extend top barn */
                min[lv].topmin += c1 - l1;

                t = l1;
                if (t < l2) t = l2;
                /* End bottom barn */
                t = min[lv].bothmin + (c1 - t);
                if (min[lv].topmin > t) min[lv].topmin = t;

                t = l1;
                if (t < l2) t = l2;

                /* Extend both barns */
                min[lv].bothmin += 2*(c1 - t);

                /* Extend spanning barn */
                min[lv].spanmin += 2*(c1 - t);

                /* Start new barn */
                t = min[lv-1].topmin;
                if (min[lv-1].botmin < t) t = min[lv-1].botmin;
                if (min[lv-1].bothmin < t) t = min[lv-1].bothmin;
                if (min[lv-1].spanmin < t) t = min[lv-1].spanmin;
                if (min[lv].topmin > t+1) min[lv].topmin = t+1;

                /* Would never want to continue bottom barn */
                /* Never want to start both barns now */
            }
            l1 = c1;
            ++i1;
        } else if (c1 == c2) {
            for (lv = nbarn; lv > 0; lv--) {
                /* No way to cover with just one barn */
                min[lv].topmin = INFTY;
                min[lv].botmin = INFTY;

                t = l1;
                if (t < l2) t = l2;
                /* Extend both barns */
                min[lv].bothmin += (c1 - t) + (c2 - t);

                /* Extend spanning barn */
                min[lv].spanmin += (c1 - t) + (c2 - t);

                /* Start new barns */
                t = min[lv-1].topmin;
                if (min[lv-1].botmin < t) t = min[lv-1].botmin;
                if (min[lv-1].bothmin < t) t = min[lv-1].bothmin;
                if (min[lv-1].spanmin < t) t = min[lv-1].spanmin;
                if (min[lv].spanmin > t+2) min[lv].spanmin = t+2;

                t = min[lv-1].botmin + (c2 - l2) + 1;
                if (t < min[lv].bothmin) min[lv].bothmin = t;

                t = min[lv-1].topmin + (c1 - l1) + 1;
                if (t < min[lv].bothmin) min[lv].bothmin = t;

                if (lv >= 2) {
                    t = min[lv-2].topmin;
                    if (min[lv-2].botmin < t) t = min[lv-2].botmin;
                    if (min[lv-2].bothmin < t) t = min[lv-2].bothmin;
                    if (min[lv-2].spanmin < t) t = min[lv-2].spanmin;
                    if (min[lv].bothmin > t+2) min[lv].bothmin = t+2;
                }
            }

            l1 = c1;
            l2 = c2;

            ++i1;
            ++i2;
        } else if (c1 < c2) {
            for (lv = nbarn; lv > 0; lv--) {
                /* No way to cover with just bottom barn */
                min[lv].botmin = INFTY;

                /* Extend top barn */
                min[lv].topmin += c1 - l1;

                t = l1;
                if (t < l2) t = l2;
                /* End bottom barn */
                t = min[lv].bothmin + (c1 - t);
                if (min[lv].topmin > t) min[lv].topmin = t;

                t = l1;
                if (t < l2) t = l2;
                /* Extend both barns */
                min[lv].bothmin += 2*(c1 - t);

                /* Extend spanning barn */
                min[lv].spanmin += 2*(c1 - t);

                /* Start new barns */
                t = min[lv-1].topmin;
                if (min[lv-1].botmin < t) t = min[lv-1].botmin;
                if (min[lv-1].bothmin < t) t = min[lv-1].bothmin;
                if (min[lv-1].spanmin < t) t = min[lv-1].spanmin;
                if (min[lv].spanmin > t+2) min[lv].spanmin = t+2;
                if (min[lv].topmin > t+1) min[lv].topmin = t+1;

                /* Continue bottom barn and start top one */
                t = min[lv-1].botmin + (c1 - l2) + 1;
                if (min[lv].bothmin > t) min[lv].bothmin = t;

                /* Never want to start both barns now */
            }
            l1 = c1;
            ++i1;
        } else if (c2 < c1) { /* Cover bottom cow */
            for (lv = nbarn; lv > 0; lv--) {
                /* No way to cover with just bottom barn */
                min[lv].topmin = INFTY;

                /* Extend bottom barn */
                min[lv].botmin += c2 - l2;

                t = l1;
                if (t < l2) t = l2;
                /* End top barn */
                t = min[lv].bothmin + (c2 - t);
                if (min[lv].botmin > t) min[lv].botmin = t;

                t = l1;
                if (t < l2) t = l2;
                /* Extend both barns */
                min[lv].bothmin += 2*(c2 - t);

                /* Extend spanning barn */
                min[lv].spanmin += 2*(c2 - t);

                /* Start new barns */
                t = min[lv-1].topmin;
                if (min[lv-1].botmin < t) t = min[lv-1].botmin;
                if (min[lv-1].bothmin < t) t = min[lv-1].bothmin;
                if (min[lv-1].spanmin < t) t = min[lv-1].spanmin;
                if (min[lv].spanmin > t+2) min[lv].spanmin = t+2;
                if (min[lv].botmin > t+1) min[lv].botmin = t+1;

                /* Continue top barn and start bottom one */
                t = min[lv-1].topmin + (c2 - l1) + 1;
                if (min[lv].bothmin > t) min[lv].bothmin = t;

                /* Never want to start both barns now */
            }
            l2 = c2;
            ++i2;
        } else {
            assert(0);
        }

        for (lv = 1; lv <= nbarn; lv++) {
            if (min[lv].spanmin > INFTY) min[lv].spanmin = INFTY;
            if (min[lv].bothmin > INFTY) min[lv].bothmin = INFTY;
            if (min[lv].botmin > INFTY) min[lv].botmin = INFTY;
            if (min[lv].topmin > INFTY) min[lv].topmin = INFTY;
        }

    }

    t = INFTY;
    for (lv = 1; lv <= nbarn; lv++) {
        if (min[lv].spanmin < t) t = min[lv].spanmin;
        if (min[lv].bothmin < t) t = min[lv].bothmin;
        if (min[lv].botmin < t) t = min[lv].botmin;
        if (min[lv].topmin < t) t = min[lv].topmin;
    }

    fprintf (fout, "%d\n", t);

    fclose(fout);
    return 0;
}