### 问题描述 野兽先辈有 $n$ 个城市和 $m$ 条路线，可以通过这些路线从一个城市运送包裹到另一个城市。对于每条路线，他知道最大包裹数量和单个包裹的成本。 他想要从城市 $1$ 发送 $k$ 个包裹到城市 $n$。求解做到这一点所花的最便宜的价钱。 ### 输入格式 第一行有三个整数 $n$，$m$ 和 $k$，表示城市数量、路线数量和包裹数量。城市编号为 $1, 2, \dots, n$。 接下来，有 $m$ 行描述路线。每行有四个整数 $a$，$b$，$r$ 和 $c$，表示从城市 $a$ 到城市 $b$ 有一条路线，最多可以通过 $r$ 个包裹，每个包裹的成本是 $c$。 ### 输出格式 输出一个整数，表示最小总成本，如果没有解决方案则打印 $−1$。 ### 样例输入 ``` 4 5 3 1 2 5 100 1 3 10 50 1 4 7 500 2 4 8 350 3 4 2 100 ``` ### 样例输出 ``` 750 ``` ### 评测数据规模 $2 \leq n \leq 500$，$1 \leq m \leq 1000$，$1 \leq k \leq 100$，$1 \leq a, b \leq n$，$1 \leq r, c \leq 1000$。