← 返回题目列表

Codeforces · 853/B

B. 评审团会议

中文机器翻译题面 查看原题

大都市之国即将举办大都市奥林匹克竞赛。这意味着奥林匹克竞赛的所有评委会成员都应该在大都会(国家首都)聚集在一起进行问题准备过程。

有 n + 1 个城市,从 0 到 n 连续编号。城市 0 是大都市,是所有评审团成员的聚会点。对于从 1 到 n 的每个城市,只有一名评审团成员居住在那里。奥运会准备工作是一个漫长而艰巨的过程,需要k天的工作。在所有这 k 天里,n 个评审团成员中的每一个都应该出现在大都会,以便能够解决问题。

您知道该国的航班时刻表(评审团成员认为自己足够重要,只使用航班作为交通)。大都会 的所有航班要么飞往大都会,要么从大都会出发。大都会没有夜间航班,换句话说,飞机总是在到达的当天起飞。在他抵达当天和离开当天,评审团成员无法讨论奥林匹克竞赛。梅加波利亚的所有航班均在同一天出发和抵达。

在首都聚集所有人 k 天是一个硬目标,而花尽可能少的钱来做到这一点则更加困难。尽管如此,你的任务是安排最便宜的方式将所有评审团成员带到大都会,让他们一起工作k天,然后将他们送回自己的家乡。安排成本定义为所有已使用航班的机票总成本。评审团成员可以在大都会停留k天以上。

输入

输入的第一行包含三个整数 n、m 和 k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106)。

以下 m 行的第 i 行包含由四个整数 di、fi、ti 和 ci 定义的第 i 个航班的描述(1 ≤ di ≤ 106、0 ≤ fi ≤ n、0 ≤ ti ≤ n、1 ≤ ci ≤ 106,fi 和 ti 正好为零)、出发(和到达)日期、出发城市、到达城市和机票费用。

输出

输出唯一的整数,即在 k 天时间内将所有评审团成员聚集在 0 城市,然后将他们送回自己的家乡所需的最低成本。

如果不可能在 k 天时间内将所有人聚集在大都会然后将他们送回自己的家乡,则输出“-1”(不带引号)。

示例

输入 #1

2 6 5
1 1 0 5000
3 2 0 5500
2 2 0 6000
15 0 2 9000
9 0 1 7000
8 0 2 6500

输出 #1

24500

输入 #2

2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000

输出 #2

-1

注意

在第一次样本测试中将所有人聚集在大都会的最佳方法是使用第 1、2、8 和 9 天的航班。唯一的替代选择是在第 15 天将第二个城市的评审团成员送回家,这将多花费 2500 美元。

在第二个样本中,不可能将城市 2 的陪审团成员从大都会送回家。