The Key Observation

Plot all lines $y = m_j x + c_j$ in the $xy$-plane. For a query point $x_i$, you want the line giving minimum $y$. Different lines win at different $x$ values.

A steep negative slope wins for small $x$. A gentle slope wins for large $x$. At any $x$, exactly one line (or a tie) gives the minimum. The set of points where each line is optimal forms the lower envelope. Only lines on this envelope ever contribute to answers. Lines strictly above it are useless.