#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <math.h>
#include <string.h>

using namespace std;

int N, H, v[1002], t[1002];
vector<vector<int> > g(1002);

int pd[1002][1002];

int func(int pos, int times){
    if(pos == H+1){
        return 0;
    }else{
        int &ans = pd[pos][times];
        if(ans == -1){
            ans = func(pos+1, times);
            if(times < pos){
                int cur_time = times;
                int sum = 0;
                for(int j = 0; j < g[pos].size() && cur_time < pos; j++){
                    sum += g[pos][j];
                    cur_time++;
                    ans = max(ans, sum + func(pos+1, cur_time));
                }

            }
        }
        return ans;
    }
}

int main(void){
    freopen("in.in", "r", stdin);
    while(cin >> N >> H){
        for(int i = 0; i <= H; i++){
            g[i].clear();
        }
        int sum = 0;
        for(int i = 0; i < N; i++){
            cin >> v[i] >> t[i];
            g[t[i]].push_back(v[i]);
            sum += v[i];
        }
        for(int i = 1; i <= H; i++){
            sort(g[i].begin(), g[i].end(), greater<int>() );
        }
        memset(pd, -1, sizeof(pd));
        cout << sum - func(0, 0) << endl;
    }
    return 0;
}