Peace abroad and concord at home are a beautiful thing.
- Inscription on an old city gate of Lubeck
Several cities have formed a trade alliance to protect merchants and promote trade. You are the accountant responsible for the alliance's common fund.
The alliance wants to encourage new trade between its member cities. For each pair of distinct member cities, it has decided to subsidize the cost of shipping one box of goods in their first transaction, once per pair.
The alliance has member cities, numbered from to . Every pair of distinct member cities is connected by a bidirectional trade route along which goods can be shipped directly. The cost of shipping one box of goods directly from city to city is
The first line contains integers and , separated by a space.
Print the total subsidy that the alliance must prepare.
In the first example, the minimum shipping costs for , , , , , and are , , , , , and , respectively. Therefore, the total subsidy required is .
Here, is a nonnegative integer, and denotes the remainder when is divided by .
Goods may also be shipped via other member cities. The shipping cost for one box is the sum of the costs of all trade routes along its path. Merchants choose a path with the minimum shipping cost. The shipping cost of each transaction is calculated independently of all other transactions.
Reversing the shipping direction does not change the minimum cost, and the alliance provides a subsidy only once for each pair of cities. Thus, the total subsidy required is the sum, over all pairs satisfying , of the minimum cost of shipping one box of goods from city to city . Find the total subsidy that the alliance must prepare.
In the second example, the minimum shipping costs for , , and are , , and , respectively. Therefore, the total subsidy required is .
