Cht

struct Cht {
  std::vector<std::pair<long long, long long>> lines;
  std::vector<long long> x;

  [[nodiscard]] long long get(long long y) const {
    int i = std::lower_bound(x.begin(), x.end(), y) - x.begin();
    assert(i < int(lines.size()));
    return lines[i].first * y + lines[i].second;
  }

  void add(long long k, long long m) {
    assert(lines.empty() || lines.back().first <= k);
    if (!lines.empty() && lines.back().first == k) {
      if (lines.back().second >= m) {
        return;
      }
      if (!x.empty()) {
        x.pop_back();
      }
      m = lines.back().second;
      lines.pop_back();
    }
    while (!x.empty() && x.back() >= (lines.back().second - m) / (k - lines.back().first)) {
      lines.pop_back();
      x.pop_back();
    }
    if (!lines.empty()) {
      x.push_back((lines.back().second - m) / (k - lines.back().first));
    }
    lines.emplace_back(k, m);
  }
};