P8385 [POI 2003] Smugglers

Byteotia 因为它丰富的金矿资源而闻名世界. 所以在和它的邻国 Bitland 的边界上每年都有大量的金矿交易。不幸的是由于税务的繁重，商人带着矿产穿过边境时都要交纳矿产价格的 $50\%$ 作为关税。但是幸运的是，有一些炼金术士已经发明了一些方法能把某一种矿产转化成另一种的矿物。于是这样在交易时就可以先把昂贵的矿产转化成便宜的，等到带过边境以后在转换回来。但是由于这项工作费时费力，炼金术士对于每种转换都要收取相应的费用。现在有个商人想将 $1$ kg 金子带过边境，他想知道最少的花费是多少。

无

无

对于 $100\%$ 的数据，$1 \le n \le 5000$，$0 \le p_k \le 10^9$，$0 \le m \le 100000$，$1 \le a,b \le n$，$0 \le c \leq 10000$。