LineContainer

namespace line_detail {
  struct Line {
    long long k;
    long long m;
    mutable long long p;

    bool operator < (const Line& ot) const {
      return k < ot.k;
    }

    bool operator < (long long x) const {
      return p < x;
    }
  };
}

struct LineContainer : std::multiset<line_detail::Line, std::less<>> {
  constexpr static long long inf = std::numeric_limits<long long>::max();

  static long long div(long long x, long long y) {
    return x / y - ((x ^ y) < 0 && x % y != 0);
  }

  bool check(iterator x, iterator y) {
    if (y == end()) {
      x->p = inf;
      return false;
    }
    if (x->k == y->k) {
      x->p = (x->m > y->m ? inf : -inf);
    } else {
      x->p = div(y->m - x->m, x->k - y->k);
    }
    return x->p >= y->p;
  }

  void add(long long k, long long m) {
    auto z = insert({k, m, 0});
    auto y = z++;
    auto x = y;
    while (check(y, z)) {
      z = erase(z);
    }
    if (x != begin() && check(--x, y)) {
      check(x, erase(y));
    }
    while ((y = x) != begin() && (--x)->p >= y->p) {
      check(x, erase(y));
    }
  }

  long long get(long long x) {
    assert(!empty());
    auto l = *lower_bound(x);
    return l.k * x + l.m;
  }
};