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:
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.
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
Name |
---|