text: typedef long long ll;
  struct CHTLinear {
      struct Line {
          ll a, b;
          ll y(ll x) const { return a * x + b; }
      };
      vector<Line> stk;
      int qpt;
      CHTLinear() : qpt(0) { }
      // when you need maximum :  (previous l).a < (now l).a
      // when you need minimum :  (previous l).a > (now l).a
      void add(const Line &l) {
          while (stk.size() > 1) {
              Line& l0 = stk[stk.size() - 1];
              Line& l1 = stk[stk.size() - 2];
              if ((l0.b - l.b) * (l0.a - l1.a) > (l1.b - l0.b) * (l.a - l0.a)) break;
              stk.pop_back();
          }
          stk.push_back(l);
      }
      // (previous x) <= (current x)
      // it calculates max/min at x
      ll query(ll x) {
          while (qpt + 1 < stk.size()) {
              Line& l0 = stk[qpt];
              Line& l1 = stk[qpt + 1];
              if (l1.a - l0.a > 0 && (l0.b - l1.b) > x * (l1.a - l0.a)) break;
              if (l1.a - l0.a < 0 && (l0.b - l1.b) < x * (l1.a - l0.a)) break;
              ++qpt;
          }
          return stk[qpt].y(x);
      }
  };