你是一個販賣可魚果的廠商。最近有一隻富有的大可魚花了他五百一十四分之一百四十五的財產訂購了大量的可魚果，導致你原本的物流機制出了些問題。無計可施的情況下，你只得把運輸可魚果的工作交給可魚國內有名的墨魚運輸公司處理。

然而，正如墨水一般黑，墨魚運輸公司雖然運輸量大、使命必達，但墨魚運輸公司所開的價碼異常昂貴。俗話說，賠錢的生意沒人作，作為一個商人，你為了避免利潤受到過多的壓縮，決定參與規劃運輸路線，使得運輸成本降到最低。

墨魚運輸公司提供了許多運輸方案，每個方案 $P_i$ 會從一個固定的起始城市 $A_i$ 運送東西到另一個固定的終點城市 $B_i$，每運輸一箱的可魚果，你就必須付給墨魚運輸公司 $C_i$ 可魚幣。另外，若兩個方案的終點與起點相接，則可以不花任何額外費用的將貨物轉過去。不過由於你的運輸量太大了，墨魚運輸公司決定祭出優惠，若用方案 $P_i$ 運輸了超過 $D_i$ 箱的可魚果，多出來的部份每箱改收優惠價 $C'_i$ 可魚幣。

你原本是隻數學挺好的可魚，但不幸的，你前些日子去東北方的日升之國談生意時感冒了，無法進行複雜的運算。你好奇運輸費究竟可以壓到多低呢？