Background

While I was learning the "Slope Trick", I could understand the examples but had a hard time solving related problems by myself. Maybe my thinking process is just different. Along the way, I come up with a different way to think about this algorithm (and come to almost the same code.) Here I would like to share how I think about it, which I call "Worse-to-best option", inspired by the "Buy Low Sell High" problem that I'll explain below.

The Slope Trick is first explained by zscoder in this tutorial, and then further explained by Kurino in this blog. I learned from Benq USACO Guide here.

"Worse-to-best option"

The help