public class ConvexHullOptimization {

	long[] A = new long[1000000];
	long[] B = new long[1000000];
	int len;
	int ptr;

	// a descends
	public void addLine(long a, long b) {
		// intersection of (A[len-2],B[len-2]) with (A[len-1],B[len-1]) must lie to the left of intersection of (A[len-1],B[len-1]) with (a,b)
		while (len >= 2 && (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2])) {
			--len;
		}
		A[len] = a;
		B[len] = b;
		++len;
	}

	// x ascends
	public long minValue(long x) {
		ptr = Math.min(ptr, len - 1);
		while (ptr + 1 < len && A[ptr + 1] * x + B[ptr + 1] <= A[ptr] * x + B[ptr]) {
			++ptr;
		}
		return A[ptr] * x + B[ptr];
	}

	// Usage example
	public static void main(String[] args) {
		ConvexHullOptimization h = new ConvexHullOptimization();
		h.addLine(3, 0);
		h.addLine(2, 1);
		h.addLine(3, 2);
		h.addLine(0, 6);
		System.out.println(h.minValue(0));
		System.out.println(h.minValue(1));
		System.out.println(h.minValue(2));
		System.out.println(h.minValue(3));
	}
}