B. Встреча жюри
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В стране Мегаполия уже подходит время проведения олимпиады Мегаполисов, и все члены жюри должны собраться в главном городе страны — Мегаполисе, чтобы подготовить задачи соревнования.

Всего в стране есть 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).

В i-й из последующих m строк находится описание i-го рейса, заданное четырьмя целыми числами di, fi, ti и ci (1 ≤ di ≤ 106, 0 ≤ fi ≤ n, 0 ≤ ti ≤ n, 1 ≤ ci ≤ 106, ровно одно из чисел fi и ti равно нулю) — днём отправления, городом отправления, городом прилёта и стоимостью билета на рейс соответственно.

Выходные данные

Выведите одно целое число — стоимость самого дешёвого способа собрать всех членов жюри в городе 0 на k дней и затем вернуть их всех в родные города.

Если собрать всех на k дней в Мегаполисе, а затем отправить всех обратно по домам невозможно, выведите «-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
Выходные данные
24500
Входные данные
2 4 5
1 2 0 5000
2 1 0 4500
2 1 0 3000
8 0 1 6000
Выходные данные
-1
Примечание

В первом примере оптимальный способ собрать всех в Мегаполисе — использовать рейсы, выполняемые в дни 1, 2, 8 и 9. Единственный альтернативный вариант, который заключается в том, чтобы отправить члена жюри из второго города домой в день 15, будет на 2500 дороже.

Во втором примере невозможно отправить домой из Мегаполиса члена жюри из города 2.