题目背景

翻译自 CSES-2121 题。

题目描述

有 $n$ 个城市和 $m$ 条路线，通过这些路线，包裹可以从一个城市运送到另一个城市。对于每条路线，你知道最大可以运输的包裹数和每个包裹的运费。

你需要将 $k$ 个包裹从 Syrjälä（城市 $1$）送到 Lehmälä（城市 $n$）。请你找出最便宜的运输方式。

输入格式

第一行包含三个整数 $n, m, k$：分别表示城市数、路线数和包裹数。城市编号从 $1$ 到 $n$，城市 $1$ 是 Syrjälä，城市 $n$ 是 Lehmälä。

接下来有 $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

提示

• 通过路线 $1 \to 2 \to 4$（$1$ 个包裹，费用 $1 \times (100+350) = 450$）运送 $1$ 个包裹。
• 通过路线 $1 \to 3 \to 4$（$2$ 个包裹，费用 $2 \times (50+100) = 300$）运送 $2$ 个包裹。
• 总费用为 $450 + 300 = 750$。

数据范围

• $2 \le n \le 500$
• $1 \le m \le 1000$
• $1 \le k \le 100$
• $1 \le a, b \le n$
• $1 \le r, c \le 1000$