Problem Description

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.

Input Format

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.

Output Format

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

6
3

12

1000
1000

32561

100000
10000

10099799

Hint

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