你作为一名市警察局局长，每天都要沿着城市的道路巡逻。这座城市共有 nnn 个地标，某些地标之间可能会有单向道路相连，这些道路共有 mmm 条，我们称这些单向道路为旧路。现在市里新修了 AAA 条单向道路，我们称这些单向道路为新路。每条旧路都有一个权值 ccc，表示通过这条道路消耗的油量；每条新路也有权值，也表示通过这条道路消耗的油量，不过权值是变化的。以第 iii 条新路为例，一开始其权值为 di0d_{i0}di0，若总共通过了 jjj 条新路，其权值就会变为 dijd_{ij}dij（在完全一条新路通过时才会改变）。不会存在两条旧路连接相同的两个地标，也不会存在两条新路连接相同的两个地标。
你的警察局位于城市的 111 号地标处，现在你需要通过恰好 kkk 条旧路和 BBB 条新路（都可以重复经过），并最终停在任意地标处。你希望知道完成这件任务最少需要消耗多少油。