Statement

William is playing his favorite game on his smartphone, where he has to grow a nation from the grounds to the sky! In this game, you have to build cities, earn money and spend it to make your nation rich and powerful. Infrastructures are also very important, and developing streets should be kept in mind at all times… but William realized only now that he has built N cities and zero roads between them! This game is very realistic, thus, you cannot build a road between two random cities as the terrain may be too steep. William knows exactly which city could be connected to which. As you may imagine, the more streets you build, the better. However, building a road is expensive: it costs 1 million dollars to each of the two city it connects, and each city has a limited budget of D_i million dollars available. Help William determine which streets to build in order to maximize the total number of roads, while keeping the costs within the budget of every city.