Cây khung nhỏ nhất

Time limit: 4.0 s
Memory limit: 512 MB
Points: 3,000partial
AC rate: 9.1%
Solvers: 9

Cho đồ thị đầy đủ gồm $N$ ~N~ đỉnh và $\frac{N(N-1)}{2}$ ~\frac{N(N-1)}{2}~ cạnh, các đỉnh được đánh số từ $1$ ~1~ đến $N$ ~N~. Mỗi đỉnh $i$ ~i~ của đồ thị được gán một trọng số dương $A_i$ ~A_i~. Giữa hai đỉnh $i$ ~i~ và $j$ ~j~ của đồ thị có cạnh nối hai chiều với trọng số được tính như sau:

$w_{i,j}=|i-j| \times D+A_i+A_j$

Trong đó $D$ ~D~ là số nguyên không âm cho trước.

Nhiệm vụ của bạn hãy tìm độ dài cây khung nhỏ nhất của đồ thị.

Input

Dòng đầu tiên chứa hai số nguyên $N$ ~N~ và $D$ ~D~ $(1 \le N \le 2 \times 10^5$ ~(1 \le N \le 2 \times 10^5~ ; $0 \le D \le 10^9)$ ~0 \le D \le 10^9)~.
Dòng thứ hai chứa $N$ ~N~ số nguyên $A_i$ ~A_i~ $(1 \le A_i \le 10^9)$ ~(1 \le A_i \le 10^9)~.

Output

In ra độ dài cây khung nhỏ nhất của đồ thị.

Examples

Sample Input

3 2
1 2 3

Sample Output

Scoring

Subtask $1$ ~1~ $-$ ~-~ $500$ ~500~ điểm: $N \le 2000$ ~N \le 2000~
Subtask $2$ ~2~ $-$ ~-~ $500$ ~500~ điểm: $A_i=A_j$ ~A_i=A_j~ với mọi $1 \le i < j \le N$ ~1 \le i < j \le N~
Subtask $3$ ~3~ $-$ ~-~ $500$ ~500~ điểm: $D=0$ ~D=0~
Subtask $4$ ~4~ $-$ ~-~ $1500$ ~1500~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ, đồ thị được mô tả như trong hình sau:

Comments

You need to sign in to write comments, reply and vote.