#include <cstdio>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>


struct Apple {
  int h, w;

  friend bool operator<(Apple const& a, Apple const& b) {
    return a.h < b.h or (a.h == b.h and a.w < b.w);
  }
  friend bool operator>(Apple const& a, Apple const& b) {
    return b < a;
  }
  friend std::ostream& operator<<(std::ostream& s, Apple const& v) {
    s << '(' << v.h << ", " << v.w << ')';
    return s;
  }
};

template<class T, class C, T C::*M>
struct sum {
  T operator()(T const& cur, C const& next) { return cur + next.*M; }
};

int solve(std::vector<Apple> apples, int H, int U) {
  if (U == 0) {
    return std::accumulate(apples.begin(), apples.end(), 0, sum<int, Apple, &Apple::w>());
  }

  std::sort(apples.begin(), apples.end(), std::greater<Apple>());

  int picked_weight = 0;
  std::vector<int> available_weights;  // NOT stored negative, unlike Python code

  int offset = U - H % U;
  if (offset == U) offset = 0;
  int top = offset - U;

  while ((apples.size() or available_weights.size()) and top <= H) {
    if (available_weights.size()) {
      picked_weight += available_weights.front();
      std::pop_heap(available_weights.begin(), available_weights.end());
      available_weights.pop_back();
      top += U;
    }
    else {
      top += U * std::max(1, (apples.back().h - top) / U);
    }

    while (apples.size() and apples.back().h <= top) {
      available_weights.push_back(apples.back().w);
      std::push_heap(available_weights.begin(), available_weights.end());
      apples.pop_back();
    }
  }

  return picked_weight;
}

template<int N>
void test(int expected, Apple (&apples)[N], int H, int U) {
  std::vector<Apple> v (apples, apples + N);
  int actual = solve(v, H, U);
  if (expected != actual) 
    std::printf("expected=%d", actual);
}

int main() {
  {
    Apple data[] = {{37000000, 2000000}, {24000000, 23000000}, {700, 48000000},
	{40000000, 48000000}, {9000000, 34000000}, {58000000, 2000000}, 
	{47000000, 38000000}, {490,	7000000}, {80000, 35000000}, {14000000,	1000000}};
    test(0, data, 70000000, 10000000);
  }
}