https://atcoder.jp/contests/dp/tasks/dp_zIt is convex hull trick. There are two ways to understrand CHT, the one is using lines, another is using points.We are given N points (a[i], b[i]) on the a-b plain. And then given $x$, please find t…