P4764 [CERC2014] Pork barrel

Winning the election was simpler than you expected: it was enough to promise to finally build a good quality, country-wide road infrastructure, of course without crippling the budget... Your happiness did not last long, however: it seems, that the citizens have found a way to actually hold you accountable for your promise! There are $n$ major cities in your country. The Ministry of Transport has prepared a detailed map, outlining $m$ possible highway connections, together with their costs. The Quality Assurance Committee will not let you build a highway cheaper than $l$, and the National Spendings Regulatory Committee will not let you build a highway more expensive than $h$. To claim a “country-wide” network, you have to connect (possibly indirectly) as many pairs of cities, as it is possible within these two constraints. You have to find the cheapest way to do it, and you have to find it quickly! Of all networks that meet the constraints and connect the most pairs of cities,compute the cost of the cheapest one. To make things worse, both committees are heavily influenced by your angry competitors:each time you publish your hard-prepared plan, they immediately change their rulings $l$ and $h$,and you are forced to start from scratch.

无

无