CF853B Jury Meeting

Metropolia 国家即将举办 Metrpolises 奥林匹克竞赛。这意味着所有奥赛的评委都需要在首都 Metropolis 集合，以便共同准备题目。 有 $n+1$ 座城市，编号从 $0$ 到 $n$。城市 $0$ 是首都 Metropolis，是所有评委集合的地点。对于每座从 $1$ 到 $n$ 的城市，正好有一位评委居住在那里。奥赛的准备是一个漫长且繁重的过程，需要持续工作 $k$ 天。在这 $k$ 天内，所有 $n$ 位评委都必须齐聚首都，才能进行出题工作。 你知道该国的航班安排（评委们自认非常重要，只使用航班出行）。在 Metropolia，所有航班要么飞往首都，要么从首都出发。该国没有夜间航班，也就是说，飞机总是在同一天起飞并到达（即出发日等于到达日）。评委在到达首都当天和离开首都当天无法参与奥赛的讨论。所有航班都在同一天完成出发与到达。 请为所有评委安排最便宜的方式，使他们能在首都共同工作 $k$ 天，然后再返回各自的家乡。总费用定义为所有使用航班的总票价。允许评委在首都停留超过 $k$ 天。

输入的第一行包含三个整数 $n$、$m$ 和 $k$，表示评委人数（不含首都）、航班数和共需工作的天数（$1 \leq n \leq 10^{5}$，$0 \leq m \leq 10^{5}$，$1 \leq k \leq 10^{6}$）。 接下来的 $m$ 行，每行描述一个航班，用四个整数 $d_i$、$f_i$、$t_i$ 和 $c_i$（$1 \leq d_i \leq 10^{6}$，$0 \leq f_i \leq n$，$0 \leq t_i \leq n$，$1 \leq c_i \leq 10^{6}$；正好有一个在 $f_i$ 和 $t_i$ 中等于 $0$），分别表示起飞（到达）日期、出发城市、到达城市和票价。

输出一个整数，表示让所有评委齐聚首都工作 $k$ 天并返回家乡所需的最小总费用。 如果无法让所有评委在首都集合并工作 $k$ 天，再安全送回各自的家乡，则输出 "-1"（不含引号）。

在第一个样例中，使所有评委在首都集合的最优方式，是选择第 $1$、$2$、$8$ 和 $9$ 天的航班。另外一种可选方式是让第二位评委在第 $15$ 天从首都返回家乡，但这会多花费 $2500$。 在第二个样例里，无法将第二位评委从首都送回家乡。 由 ChatGPT 5 翻译