Cuộc họp ban giám khảo

Có $n+1$ thành phố đánh số từ $0$ đến $n$. Thành phố $0$ là thủ đô, nơi cần tập trung toàn bộ ban giám khảo. Với mỗi thành phố từ $1$ đến $n$ có đúng một thành viên ban giám khảo sinh sống ở đó.

Quá trình chuẩn bị kỳ thi cần $k$ ngày làm việc. Trong cả $k$ ngày này, tất cả $n$ thành viên phải cùng có mặt tại thủ đô để làm việc.

Bạn biết lịch bay của cả nước. Mọi chuyến bay hoặc bay tới thủ đô, hoặc bay đi khỏi thủ đô. Không có chuyến bay đêm: mỗi chuyến bay cất cánh và hạ cánh trong cùng một ngày. Trong ngày bay đến cũng như ngày bay đi, thành viên đó không thể tham gia làm việc.

Nói cách khác, nếu một thành viên bay tới thủ đô vào ngày $a$ và bay về vào ngày $b$, thì các ngày làm việc của họ là các ngày từ $a+1$ đến $b-1$. Để cả $n$ thành viên cùng làm việc được $k$ ngày, cần tồn tại $k$ ngày liên tiếp mà mọi thành viên đều đã đến (trước đó) và chưa về (sau đó). Thành viên có thể ở lại thủ đô lâu hơn $k$ ngày.

Hãy sắp xếp cách rẻ nhất để đưa toàn bộ ban giám khảo về thủ đô làm việc chung $k$ ngày rồi đưa họ trở về thành phố của mình. Chi phí bằng tổng giá vé của tất cả các chuyến bay được sử dụng. Nếu không thể, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $m$ dòng tiếp theo, mỗi dòng mô tả một chuyến bay bằng bốn số nguyên $d_i$, $f_i$, $t_i$, $c_i$: ngày bay, thành phố đi, thành phố đến và giá vé. Đúng một trong hai giá trị $f_i$ và $t_i$ bằng $0$.

Dữ liệu ra

Một số nguyên duy nhất là chi phí nhỏ nhất, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le m\le {10}^5$
• $1\le k\le {10}^6$
• $1\le d_i\le {10}^6$
• $0\le f_i,t_i\le n$, đúng một trong $f_i$, $t_i$ bằng $0$
• $1\le c_i\le {10}^6$

Ví dụ