Jury Meeting

Country of Metropolia가 곧 Olympiad of Metrpolises를 개최한다. 이는 올림피아드의 모든 심사위원이 문제 준비 과정을 위해 Metropolis(이 나라의 수도)에 함께 모여야 한다는 뜻이다.

0부터 n까지 연속으로 번호가 매겨진 n + 1개의 도시가 있다. 도시 0은 모든 심사위원의 집결지인 Metropolis이다. 1번 도시부터 n번 도시까지 각각 정확히 한 명의 심사위원이 살고 있다. 올림피아드 준비는 k일간의 작업이 필요한 길고 고된 과정이다. 이 k일 모두에 걸쳐 n명의 심사위원은 각자 문제를 다룰 수 있도록 Metropolis에 있어야 한다.

당신은 이 나라의 항공편 일정을 알고 있다(심사위원들은 자신들이 교통수단으로 항공편만 이용할 만큼 중요하다고 생각한다). Metropolia의 모든 항공편은 Metropolis로 향하거나 Metropolis에서 출발한다. Metropolia에는 야간 항공편이 없다. 다시 말해, 비행기는 도착하는 날과 같은 날에 항상 이륙한다. 심사위원은 도착일과 출발일에는 올림피아드에 관해 논의할 수 없다. Megapolia의 모든 항공편은 같은 날 출발하고 도착한다.

모두를 수도에 k일 동안 모으는 것은 어려운 목표이며, 가능한 한 최소한의 비용으로 그렇게 하는 것은 더욱 어렵다. 그럼에도 당신의 임무는 모든 심사위원을 Metrpolis로 데려와 k일 동안 함께 일하게 한 뒤 각자의 고향 도시로 돌려보내는 가장 저렴한 방법을 마련하는 것이다. 이 계획의 비용은 이용한 모든 항공편의 항공권 비용 총합으로 정의한다. 심사위원이 Metropolis에 k일보다 더 오래 머무르는 것은 허용된다.

입력의 첫째 줄에는 세 정수 n, m, k (1 ≤ n ≤ 105, 0 ≤ m ≤ 105, 1 ≤ k ≤ 106)가 주어진다.

이어지는 m개 줄 중 i-th 줄에는 네 정수 di, fi, ti, ci (1 ≤ di ≤ 106, 0 ≤ fi ≤ n, 0 ≤ ti ≤ n, 1 ≤ ci ≤ 106, exactly one of fi and ti equals zero)로 정의되는 i-th 항공편의 설명이 주어진다. 각각 출발일(이자 도착일), 출발 도시, 도착 도시, 항공권 비용이다.

모든 심사위원을 도시 0에 k일 동안 모은 뒤 각자의 고향 도시로 돌려보내는 데 필요한 최소 비용인 유일한 정수를 출력한다.

모두를 Metropolis에 k일 동안 모은 뒤 각자의 고향 도시로 돌려보내는 것이 불가능하면 "-1"을 출력한다(따옴표 제외).

첫 번째 예제 테스트에서 모두를 Metropolis에 모으는 최적의 방법은 1일, 2일, 8일, 9일에 운항하는 항공편을 이용하는 것이다. 유일한 다른 선택지는 두 번째 도시의 심사위원을 15일에 집으로 돌려보내는 것이며, 그러면 비용이 2500만큼 더 든다.

두 번째 예제에서는 도시 2의 심사위원을 Metropolis에서 집으로 돌려보내는 것이 불가능하다.