『醒醒啊、醒醒啊！』

你感覺到有一隻手搭在自己肩上，然後劇烈地搖晃起你的身子，然後你就醒了。

「呼原來這都是一場夢啊，那什麼烏龜什麼的鬼世界……」你發現自己全身都冒著冷汗
──做了一場自己掉入烏龜世界的夢，誰能不冷汗直冒？

不過，你想著，有著幸福美滿結局就好了，你望了一下搖醒你的人。

然後對上的是一隻烏龜的臉。

你知道惡夢還要持續蔓延。

『嘿你已經睡了半個小時了！在這種危機關頭還要打混！』那隻烏龜很生氣地望著我。

到底還是在夢中嗎，你這樣想著，又閉上了眼睛。

但沒隔多久就又被搖醒，你只好睜開了眼，環顧四周。

這是一塊光禿禿的高地，許多隻烏龜在附近來回走動(以那種速度實在不能被稱為奔波)，
他們看起來又跟皇宮那些嬌生慣養的不一樣，每隻都長得結實精幹補粗。

「這是在哪……我不是在烏龜館嗎？」你納悶著，但是接著搖醒你的烏龜馬上幫你做了解釋。
『你怎麼可能在烏龜館裡面！如果你能混得進去我們早就把國王做掉了！不要再做無聊的妄想吧，來準備一下計畫！』。

接著他──你後來知道了他叫做羅柏柯，簡稱RK。遞給了你一張地圖，跟你解釋著：

這張地圖上面標示了許多連接城與城之間的雙向道路。每條道路上都有一座收費站。每
座收費站每個方向(沒錯，同一個收費站不同方向過路費也會不一樣)都有一個起始過路費C ，
在第一天時收費就是C元。但是還有一個費用變量P，每一天結束在下一天開始之前，
會把該方向過路費調整P ( 元 正表示過路費調昇、負表示調降)。

也就是說，第T天的費用為C+(T-1)×P。

你們已經調查出了國王居住的城市跟皇后居住的城市，
而且知道國王一定會在[1,D](包含1 和 D)的某一天去拜訪皇后再在當日回到國王城市。

國王嗜錢如命，自然希望這一趟旅行過路費儘量少。

請你輸出國王選了最划算的日子拜訪皇后之下，所需要支付的總過路費。