P11258 [GDKOI2023 Junior] City Construction

There are $N$ cities located at nodes $1, 2, ..., N$. As the manager of the cities, Xiaoming wants to connect these $N$ cities with the minimum total cost. The cost of connecting cities mainly consists of the following two types. Type 1: Build roads. Building a road between city $a$ and city $b$ costs $|a - b|$. Type 2: Set up management cities. For a city $X$, you can upgrade it to a management city at a cost of $C$. Under the constraints that every road must be incident to at least one management city, and every non-management city can connect to only one edge, Xiaoming wants to know the minimum total cost to make all cities connected.

The first line contains a positive integer $N$, representing the number of cities. The second line contains an integer $C$, representing the cost to set up a management city.

One line containing one integer, representing the minimum cost for Xiaoming to connect all cities.

### Sample Explanation The minimum cost can be achieved by taking $2$ and $5$ as management cities, and connecting the five edges $(1, 2)$, $(2, 3)$, $(2, 5)$, $(4, 5)$, $(5, 6)$. It can also be achieved by taking $3$ or $4$ as the management city and connecting all other nodes to it, which also gives the minimum cost. ### Constraints For $20\%$ of the testdata, $1 \le N \le 20$. For $40\%$ of the testdata, $1 \le N \le 10^3$. For another $20\%$ of the testdata, $1 \le N \le 10^5$, $0 \le C \le 10^4$. For $100\%$ of the testdata, $1 \le N \le 10^9$, $0 \le C \le 10^9$. Translated by ChatGPT 5