19071번 - Build the Graph 다국어

문제

For an undirected graph $G$ with $n$ nodes and $m$ edges, we can define the distance $\textit{dist} (i, j)$ as the length of the shortest path between nodes $i$ and $j$. The length of a path is equal to the number of edges in the path. If there is no path between $i$ and $j,ドル we set $\textit{dist} (i, j)$ equal to $n$.

Then, we can define $w_G,ドル the weight of the graph $G,ドル as $\sum_{i = 1}^n \sum_{j = 1}^n \text{dist} (i, j)$.

Now, given $n$ nodes and no edges initially, we will choose no more than $m$ pairs of nodes $(i, j)$ ($i \neq j$) and add an edge between the respective nodes for every chosen pair. This way, we can get an undirected graph $G$ with $n$ nodes and no more than $m$ edges.

Your task is to find the minimal possible value of $w_G$ after such construction.

입력

The first line of the input contains two integers $n$ and $m$ (1ドル \leq n \leq 10^6,ドル 1ドル \leq m \leq 10^{12}$).

출력

Print a single line with a single integer: the minimum possible value of $w_G$.

제한

힌트

In the example, we can choose to add edges $(1, 2),ドル $(1, 4),ドル $(2, 4),ドル $(2, 3)$ and $(3, 4)$.