前情提要。

總之，在某個神奇的世界裡，有N座城市，每座城市從0編號到N-1。有M條雙向道路，每條連接兩個不同的城市。
這個世界很完備(?)，所以不必擔心有兩座城市不能經由這些道路通行的狀況發生。

每條道路上都有兩座收費站，分別對不同方向的人收費。每個收費站（沒錯，同一條道路不同方向過路費也會不一樣）都有一個起始過路費$C$，在第0天時收費就是$C$元。
但特別的是，每座收費站每個方向還有一個費用變量$P\in \mathbb{Z}$，代表每一天結束在下一天開始之前，會把該方向過路費調整$P$元。（正表示過路費調昇、負表示調降、0代表費用一直不變。）
也就是說，第$T$天的過路費為$C+TP$。

你和某個你想陷害的人Q，現在都位於城市$A$。恰好，你們都有一件重要的事情要去城市$B$辦，而截止日期是第$D$天。
也就是說，你們可以在第0天到第$D-1$天的任一天去辦事，但是不能在第$D$天（含）以後才去辦。
而你們這段時間都很閒想待在家裡，所以你們的路線一定是$A\to B\to A$。

你預先調查好了每一條道路的過路費資訊，希望能說服Q在某一天去辦事，而你自己也選一天去辦事，使得他比你多付的過路費愈多愈好。
假如說你可以說服Q，並且你一定會走對路，求在最好的策略之下，他至少會比你多付多少元的過路費。