In the cat country, there are cities. The cat country king wants to build roads to connect all the cities. The -th city has a construction company with an experience value of . To build a road between the -th city and the -th city, the two cities' construction companies need to cooperate with each other. However, in the process of building a road, the two construction companies may have conflicts due to poor communication, and it will result in a waste of building materials. Formally, building a road between the -th city and the -th city will waste  building materials.

Can you help the cat country king choose to build roads that connect all the cities and minimize the waste of building materials?

To decrease the input size, the king of the cat country gives you a random integer generator and parameters . The following C language code shows how to generate integers , and stores the experience value of the construction company of the -th city. You can use the code directly in your submissions.