Minimum Cost to Connect Cities with Management Upgrades

There are N cities located at nodes 1, 2, …, N on a line. As the administrator, Xiao Ming wants to connect all these cities with minimum cost. There are two ways to incur cost:

• Build a road: Connecting city a and city b costs \( |a - b| \).
• Upgrade a city to a management city: Upgrading a city \(X\) costs a fixed amount \(C\).

The final network (a spanning tree) must satisfy the following conditions:

• Every road (edge) must have at least one endpoint that is a management city.
• A non-management city can be incident to at most one road (i.e. it must be a leaf in the tree).

A feasible structure is to choose a set \(M\) of management cities. All management cities can be interconnected arbitrarily (for example, in a chain) and every non-management city is attached as a leaf to one of its nearest management cities. In particular, if there is exactly one management city, then every other city is attached directly to it, and the cost to attach a city \(i\) (if the management city is at \(m\)) is \( |i - m| \).

The task is: given \(N\) and \(C\), determine the minimum total cost to connect all the cities such that the above conditions hold.

Note: In the tree you build, for any segment of consecutive cities attached to a management city located at position \(i\), if these cities are \(l, l+1, \dots, i-1\) (to the left of \(i\)) or \(i+1, i+2, \dots, r\) (to the right), the cost for connecting them is the sum of distances (i.e. \(\sum (i - x)\) or \(\sum (x - i)\)). Moreover, when connecting two management cities located at \(j\) and \(i\) (with \(j < i\)), you need to add a road cost \(i-j\) as well as the attachment cost for cities in between if they are attached to the new management city. These details lead to a dynamic programming formulation which runs in \(O(N^2)\) time.

Input Format: The first line contains two integers \(N\) and \(C\) separated by a space.

Output Format: Print a single integer which is the minimum cost to connect all the cities.

inputFormat

The input consists of a single line containing two integers \(N\) and \(C\) (\(1 \leq N \leq 2000\), \(C \ge 0\)).

outputFormat

Output a single integer representing the minimum total cost to connect the cities under the given conditions.

sample

3 10

12