If you have Li Chao Tree, you can implement a solution easily. Remember that Li Chao Tree is a data structure which can

1. add a point $(a,\ b)$ to the set $S$
2. for a given $x$, calculate $\max\{ax+b\ |\ (a,\ b) \in S\}$

Ref: yaketake-san’s post (Japanese)

In this problem, note \(ax+by=b\cdot (\displaystyle\frac{\ a\ }{b}\cdot x+y)\). What we should do is to add \((x,\ y)\) to \(S\), and get the maximum (or minimum) at the point \(\displaystyle\frac{\ a\ }{b}\). Note that allocation of variables are different from the explanation in 1. and 2. above.

Also note:

• You need maximum or minimum depending on the sign of \(b\)
• You need an exception in case of \(b=0\)
• Float calculation can cause an error issue

AC solution（PyPy3） We used arbitrary precision integer in Python to avoid an error issue.