公式解説 の解法に考察を加えて \(O(N)\) で解く方法を紹介します。公式解説にあるとおり

1. 下側凸包に含まれる頂点
2. 下側凸包の線分

のすべてを調べれば良いです。 2. については、直線 \(x=y\) をまたぐ部分のみ調べれば良いです。これは \(x>y\) の部分（\(A\) とします）と \(x<y\) の部分（\(B\) とします）の境目の、高々 1 箇所しかないです。

プロットする頂点たちを \(A\) と \(B\) に分類し、それぞれで \(x+y\) が最小のものを選ぶと、これらの 2 つのどちらかは使われることが分かります（境目の 2 点を結ぶ傾きが \(-1\) より大きいかどうかで場合分けすれば分かります）。

具体的に下側凸包を構築する必要はなく、 1. については \(N\) 頂点を全部調べればよく、 2. についても上記の方法で \(A\) 、 \(B\) それぞれのグループの \(x+y\) が最小のものと、もう一方のグループの組をすべて調べれば良いです。

AC コード （PyPy3）