파업

바이트랜드에는 세계에서 가장 큰 갈탄 광산이 있습니다. 매일 광산에서 캐낸 석탄은 철도망을 통해 바이트랜드의 모든 도시로 운반되어, 주민들이 난로에 땔 연료로 쓰입니다.

운반 방식은 다음과 같습니다. 먼저 광산이 있는 도시에서 여러 대의 기차가 다른 몇몇 도시로 출발하고, 그 도시들에서 다시 다른 도시로 기차가 출발하는 식으로 이어집니다. 바이트랜드의 모든 도시에 대해, 광산의 석탄을 기차 $p_1$에 실은 뒤 $i = 1, \dots, k-1$에 대해 차례로 석탄을 기차 $p_i$에서 기차 $p_{i+1}$로 옮겨 싣고, 마지막으로 기차 $p_k$가 그 도시에 도착하는 기차 열 $p_1, p_2, \dots, p_k$가 적어도 하나 존재합니다. (광산이 있는 도시를 제외한) 각 도시에는 여러 대의 기차가 도착할 수 있지만, 순환은 없습니다. 즉 어떤 도시에서 기차에 타면 철도를 따라 다시 그 도시로 돌아올 수는 없습니다.

기차들은 서로 연계되어 운행됩니다. 출발 시각은, 어떤 도시에서 떠나는 기차가 그 도시로 오기로 예정된 모든 석탄 기차가 도착한 뒤에야 출발하도록 정해져 있습니다. 한 기차가 늦어지면 그로 인해 다른 기차들까지 늦어질 수 있습니다. 철도 노동자들은 파업을 계획하고 있습니다. 이들은 정확히 한 대의 기차를 $k$분 동안 붙잡아 둘 수 있습니다. 모든 기차의 지연 시간 합이 최대가 되도록 붙잡을 기차를 고르려고 합니다.

이때 만들 수 있는 최대 지연 시간 합을 구하세요.

첫째 줄에 두 정수 $n$과 $m$ ($2 \le n \le 400$, $1 \le m \le 80\,000$)이 주어집니다. 각각 바이트랜드의 도시 수와 직행 철도 연결의 수입니다. 둘째 줄에는 정수 $k$ ($1 \le k \le 10^9$)가 주어집니다. 노동자들이 기차 한 대를 붙잡아 둘 수 있는 시간(분)입니다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있고, 광산은 $1$번 도시에 있습니다.

이어지는 $m$개의 줄에는 각각 네 정수 $a_i$, $b_i$, $w_i$, $p_i$ ($1 \le a_i, b_i \le n$, $0 \le w_i, p_i \le 10^9$, $0 \le w_i + p_i \le 10^9$)가 주어집니다. 이는 $i$번째 기차가 일정대로라면 해가 뜬 뒤 정확히 $w_i$분에 도시 $a_i$에서 출발하여, 같은 날 정확히 $p_i$분 뒤에 도시 $b_i$에 도착함을 뜻합니다. (바이트랜드의 하루는 $10^9 + 1$분입니다.) 모든 도시에 대해, 그 도시에서 출발하는 기차들의 출발 시각은 그 도시로 도착하는 기차들의 도착 시각 중 가장 큰 값보다 작지 않습니다.

파업으로 노동자들이 만들 수 있는 기차들의 지연 시간 합의 최댓값을 정수 하나로 출력하세요.

예를 들어, 도시 $1$에서 도시 $3$으로 가는 기차를 $3$분 동안 붙잡으면, 그 기차뿐 아니라 도시 $3$에서 출발하는 두 기차도 함께 지연됩니다.