题目背景

翻译自 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解释

• 通过路线$1→2→4$（$1$个包裹，费用$1 \times 450 = 450$）运送$1$个包裹。
• 通过路线$1→3→4$（$2$个包裹，费用$2 \times 150 = 300$）运送$2$个包裹。
• 总费用为$450 + 300 = 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$。