const long long maxk = 1e8 + 113;
const long long maxb = 1e18 + 113;
const long long inf = 2e18;

struct line {
	long long k, b;
	line()
	{
		this->k = 0;
		this->b = 0;
	}
	line(long long k, long long b)
	{
		this->k = k;
		this->b = b;
	}
	long long func(long long x)
	{
		return k * x + b;
	}
};


struct LiChao {
	vector<line> ms;
	vector<int> le, re;
	long long range;
	LiChao() {
		this->range = maxk - 113;
		ms.push_back(line());
		le.push_back(-1);
		re.push_back(-1);
	}
	LiChao(long long range) {
		this->range = range;
		ms.push_back(line());
		le.push_back(-1);
		re.push_back(-1);
	}
	void clear() {
		ms.clear();
		le.clear();
		re.clear();
		ms.push_back(line());
		le.push_back(-1);
		re.push_back(-1);
	}
	void push(int v, bool e)
	{
		if (!e && le[v] == -1)
		{
			le[v] = ms.size();
			ms.push_back(ms[v]);
			le.push_back(-1);
			re.push_back(-1);
		}
		if (e && re[v] == -1)
		{
			re[v] = ms.size();
			ms.push_back(ms[v]);
			le.push_back(-1);
			re.push_back(-1);
		}
	}
	void add(int v, long long l, long long r, line in)
	{
		long long m = (l + r) >> 1;
		if (l > r)
			return;
		if (in.func(m) > ms[v].func(m))
			swap(in, ms[v]);
		if (l == r)
			return;
		if (in.func(l) > ms[v].func(l))
		{
			push(v, 0);
			add(le[v], l, m, in);
		}
		else
		{
			push(v, 1);
			add(re[v], m + 1, r, in);
		}
	}
	void add(line in)
	{
		add(0, -range, range, in);
	}
	long long get(int v, long long l, long long r, long long x)
	{
		if (l >= r)
			return ms[v].func(x);
		long long m = (l + r) >> 1;
		if (x <= m)
		{
			if (le[v] == -1)
				return ms[v].func(x);
			//push(v, 0);
			return max(get(le[v], l, m, x), ms[v].func(x));
		}
		else
		{
			//push(v, 1);
			if (re[v] == -1)
				return ms[v].func(x);
			return max(get(re[v], m + 1, r, x), ms[v].func(x));
		}
	}
	long long get(long long x)
	{
		return get(0, -range, range, x);
	}
};