Submission #19562216

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;
typedef map<ll, ll> mll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
// ALLの注意点
// https://kimiyuki.net/blog/2015/09/25/competitive-programming-coding/
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())
#define REVERSE(x) reverse(ALL(x))
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define SUM(x) accumulate(ALL(x), (ll)0)
#define COUNT(x, y) count(ALL(x), y);

ll tousa_no_wa(ld a, ll n, ld d) {
  return (ld(n) / (ll)2) * ((ll)2 * a + (n - (ll)1) * d);
}

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

// 素因数分解
map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if(n != 1) ret[n] = 1;
  return ret;
}

// 素数テーブル
vector<bool> prime_table(ll n) {
  vector<bool> prime(n + 1, true);
  if(n >= 0) prime[0] = false;
  if(n >= 1) prime[1] = false;
  for(int i = 2; i * i <= n; i++) {
    if(!prime[i]) continue;
    for(int j = i + i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}

// 素数判定
bool is_prime(ll x) {
  for(ll i = 2; i * i <= x; i++) {
    if(x % i == 0) return false;
  }
  return true;
}

// 約数列挙
vll divisor(ll n) {
  vll ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  SORT(ret);
  return (ret);
}

// 各桁の値リスト（k進数のとき）
vll digit_val(ll n, ll k) {
  vll ans;
  while(n != 0) {
    ans.push_back(n % k);
    n /= k;
  }
  return ans;
}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

// PRINT
// ----------------------------------------
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;

// DEBUG
// ----------------------------------------
/* 
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}
*/

#define LINE cerr << "[debug] line: " << __LINE__ << "\n";
#define debug(...) {debug_all(#__VA_ARGS__, __VA_ARGS__);}

template < typename T >
void debug_print(T const& a){
  cerr << a << ", ";
}

template < typename... Args >
void debug_all(string s, Args... args) {
  cerr << "[debug] " << s << " = ";
  using swallow = std::initializer_list<int>;
  (void)swallow{ (void( debug_print(args) ), 0)... };
  cerr << endl;
}

#define debugV(v)                       \
  cerr << "[debugV] " << #v << ":";     \
  REP(z, v.size()) cerr << " " << v[z]; \
  cerr << "\n";
// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// gcc限定
int bitCount(ll bit) {
  return __builtin_popcount(bit);
}

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


struct UnionFind {
  vll data;
 
  UnionFind(ll sz) {
    data.assign(sz, -1);
  }
 
  bool unite(ll x, ll y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return (false);
    }
    if (data[x] > data[y]) {
      swap(x, y);
    }
    data[x] += data[y];
    data[y] = x;
    return (true);
  }
 
  ll find(ll k) {
    if(data[k] < 0) {
      return (k);
    }
    return (data[k] = find(data[k]));
  }
 
  ll size(ll k) {
    return (-data[find(k)]);
  }

  ll same(ll x, ll y) {
    return (find(x) == find(y));
  }
};

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

// 二項係数ライブラリ
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

/* SegTree<X>(n,fx,ex): モノイド(集合X, 二項演算fx, 単位元ex)についてサイズnで構築
    set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
    
    遅延セグメント木や使い方は以下参考
    https://algo-logic.info/segment-tree/
*/
template <typename X>
struct SegTree {
  using FX = function<X(X, X)>; // X•X -> X となる関数の型
  int n;
  FX fx;
  const X ex;
  vector<X> dat;
  SegTree(int n_, FX fx_, X ex_) : n(), fx(fx_), ex(ex_), dat(n_ * 4, ex_) {
    int x = 1;
    while (n_ > x) {
      x *= 2;
    }
    n = x;
  }

  void set(int i, X x) { dat[i + n - 1] = x; }
  X get(int i) { return dat[i + n - 1]; }
  void build() {
    for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
  }

  void update(int i, X x) {
    i += n - 1;
    dat[i] = x;
    while (i > 0) {
      i = (i - 1) / 2;  // parent
      dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }

  X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
  X query_sub(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) {
      return ex;
    } else if (a <= l && r <= b) {
      return dat[k];
    } else {
      X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
      X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
      return fx(vl, vr);
    }
  }
};

// priority_queue<Pair, vector<Pair>, second_order> q;
struct second_order {
  bool operator()(const Pair& x, const Pair& y) const {
    return x.second < y.second;
  }
};

// その他困ったらここ
// https://ei1333.github.io/luzhiled/

void Main() {
  ll n, m;
  cin >> n >> m;

  Graph s(m);
  
  REP(i, n) {
    ll a, b;
    cin >> a >> b;
    if (a > m) continue;
    s[m - a].push_back(b);
  }

  ll ans = 0;
  priority_queue<ll> q;

  REPD(i, m) {
    for(ll j: s[i]) {
      q.push(j);
    }
    if (q.empty()) continue;
    ans += q.top();
    q.pop();
  }
  COUT(ans);
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}


/*

3 2
*/

Submission Info

Judge Result