Tối ưu hóa mạng lưới

Trong Vương quốc TIU, có \(N\) thành phố, được đánh số từ \(1\) đến \(N\). Các thành phố này được kết nối bởi \(M\) tuyến đường một chiều. Cụ thể, tuyến đường thứ \(i\) cho phép di chuyển trực tiếp từ thành phố \(u_i\) đến thành phố \(v_i\), nhưng không thể đi ngược lại.

Do nhu cầu đảm bảo an ninh và kiểm soát dịch bệnh, chính phủ Vương quốc TIU quyết định tái cấu trúc lại \(M\) tuyến đường này. Mục tiêu là sau khi tái cấu trúc, đối với mỗi thành phố \(x\), số lượng thành phố có thể đi trực tiếp đến \(x\) (hay còn gọi là bậc vào) phải tối đa là \(K\).

Việc tái cấu trúc đi kèm với chi phí. Đối với tuyến đường thứ \(i\) ban đầu (từ \(u_i\) đến \(v_i\)), chính phủ có thể chọn một trong ba phương án sau:

- Giữ nguyên: Không làm gì cả. Tuyến đường vẫn là \(u_i \to v_i\). Chi phí là \(0\).
  - Đảo chiều: Tốn \(a_i\) đồng và đảo ngược hướng đi. Tuyến đường mới sẽ là \(v_i \to u_i\).
  - Đóng hoàn toàn: Tốn \(b_i\) đồng và loại bỏ tuyến đường này khỏi mạng lưới.

**Yêu cầu: **
Hãy giúp chính phủ Vương quốc TIU tìm ra phương án tái cấu trúc với tổng chi phí thấp nhất, sao cho điều kiện về bậc vào (mỗi thành phố có tối đa \(K\) đường đi trực tiếp vào) được thỏa mãn.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, M, K\).

• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(u_i, v_i, a_i, b_i\) mô tả tuyến đường ban đầu từ \(u_i\) đến \(v_i\).

• \(1 \le N \le 500\)

• \(0 \le M \le \min(3000, \frac{N \times (N - 1)}{2})\)
• \(0 \le K \le N - 1\)
• \(1 \le u_i, v_i \le N, u_i \neq v_i\)
• \(0 \le a_i, b_i \le 10^9\)
• Đảm bảo rằng tuyến đường \((u, v)\) và \((v, u)\) sẽ không xuất hiện đồng thời trong dữ liệu.

Output

• In ra một dòng duy nhất chứa một số nguyên là tổng chi phí tái cấu trúc tối thiểu.

Example

3 3 1
1 2 2 5
3 2 1 5
3 1 10 10

1

3 3 1
1 2 100 100
2 3 100 100
3 1 100 100

0

Scoring

• Subtask 1 (30%): \(N, M, K \le 20\).
• Subtask 2 (20%): \(K = 0\).
• Subtask 3 (20%): \(K = 1\).
• Subtask 4 (30%): Không có ràng buộc gì thêm.