408812: GYM103328 I Road Reconstruction

There are $$$N$$$ cities in the NCPC Kingdom, numbered from $$$1$$$ to $$$N$$$. The cities are connected by $$$M$$$ one-way roads, where one can travel from city $$$u_i$$$ to city $$$v_i$$$ directly using the $$$i$$$-th road (but not the other way around).

Due to the new zeta variant of COVID-19, the government of the NCPC Kingdom decides to restrict people from traveling between cities. Specifically, the government wants to reconstruct the $$$M$$$ roads so that for each city $$$x$$$, there are at most $$$K$$$ other cities that can directly travel to city $$$x$$$ using a single road after the reconstruction.

The reconstruction is of course costly. For the $$$i$$$-th road, the government can choose one of the following plan:

• Do nothing.
• Spend $$$a_i$$$ dollars and reverse the road. That is, after the reconstruction, people can travel from city $$$v_i$$$ to city $$$u_i$$$ (but not the other way around).
• Spend $$$b_i$$$ dollars and shutdown the road completely.

Please help the NCPC Kingdom find the most cost-efficient reconstruction plan.

The first line of the input contains three integers $$$N$$$, $$$M$$$, and $$$K$$$. $$$M$$$ lines follow, and the $$$i$$$-th of which contains four integers $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, and $$$b_i$$$ describing the $$$i$$$-th road.

• $$$1 \leq N \leq 500$$$
• $$$0 \leq M \leq \min(3000, \frac{N \times (N - 1)}{2})$$$
• $$$0 \leq K \leq N - 1$$$
• $$$1 \leq u_i, v_i \leq N$$$, $$$u_i \neq v_i$$$
• $$$0 \leq a_i, b_i \leq 10^9$$$
• It's guaranteed that $$$(u, v)$$$ and $$$(v, u)$$$ will not appear in the input at the same time

Output a single line with an integer denoting the minimum reconstruction fee.

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