Làng Ốc Sên gồm một vòng \(n\) cây nấm khổng lồ, đánh số từ \(1\) đến \(n\). Bên cạnh mỗi cây nấm có \(n-1\) biển chỉ đến tất cả các cây nấm khác, tổng cộng \(n(n-1)\) biển.

Trên một số biển có ghi \(m\) đoạn số liên tiếp. Biển đặt cạnh nấm \(u_i\) và chỉ đến nấm \(v_i\) mang mọi số từ \(a_i\) đến \(b_i\). Các biển ban đầu thỏa hai quy tắc rõ ràng:

1. Biển cạnh nấm \(u_i\) không được chứa số \(u_i\), tức \(u_i<a_i\) hoặc \(b_i<u_i\).
2. Hai đoạn trên các biển cạnh cùng một cây nấm không được chứa chung một số. Nếu \(i\ne j\) và \(u_i=u_j\) thì \(b_i<a_j\) hoặc \(b_j<a_i\).

Không có ràng buộc tương ứng nào đối với \(v_i\).

Một con ốc đang ở nấm \(c\) muốn đến nấm \(d\). Nếu \(c=d\), nó đã đến nơi. Nếu không, nó tìm trong các biển cạnh nấm \(c\) biển có chứa số \(d\), đi theo biển đó tới \(v_i\), rồi lặp lại. Nhờ hai quy tắc trên, tại mỗi cây nấm có nhiều nhất một biển chứa \(d\).

Ốc bị kẹt nếu không tìm được biển chứa \(d\); nó cũng có thể đi vào chu trình vô hạn mà không qua \(d\).

Độ hữu dụng của hệ thống biển là số cặp có thứ tự \((s,d)\) sao cho ốc xuất phát ở \(s\) có thể đến \(d\) bằng cách đi theo các biển.

Được phép thực hiện nhiều nhất \(k\) chỉnh sửa. Mỗi chỉnh sửa là thêm một số vào một biển hoặc xóa một số khỏi một biển. Sau chỉnh sửa, hai quy tắc rõ ràng vẫn phải được thỏa mãn; các số trên mỗi biển không nhất thiết còn tạo thành một đoạn liên tiếp.

Hãy tìm độ hữu dụng lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa \(n,m,k\).
• \(m\) dòng tiếp theo, dòng thứ \(i\) chứa \(u_i,v_i,a_i,b_i\).

Dữ liệu ra

In một số nguyên: độ hữu dụng lớn nhất sau không quá \(k\) chỉnh sửa.

Giới hạn

Dữ liệu bảo đảm hai quy tắc rõ ràng nêu trong đề.

Chấm điểm

Ví dụ

6 7 0
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

8

6 7 1
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

10

6 7 2
1 2 2 3
2 5 3 3
2 5 6 6
4 5 2 3
5 4 1 1
5 6 3 3
6 1 2 5

13