#P10354. connect

    ID: 9472 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2200提高+/省选-最小生成树候选边稀疏化分治算法Kruskal普通并查集交换论证

connect

题目描述

你有 nn 个城市,你需要建立 n−1n-1 条边将其联通。

连接任意两点 i,ji,j 都有边,其边权为 ai+aj+d⋅∣i−j∣a_i+a_j+d\cdot |i-j|。

你需要求最小的边权和满足条件。

输入格式

第一行两个整数 n,dn,d。

第二行 nn 个整数 aia_i。

输出格式

一个整数表示答案。

样例输入

4 10
1 100 200 5

样例输出

362

数据范围

本题设有subtask。

对于所有数据,满足 n≤2⋅105,1≤d,ai≤109n\leq 2\cdot 10^5, 1\leq d,a_i\leq 10^9

subtask1(30),n≤5000n\leq 5000

subtask2(30),d,ai≤2⋅105d,a_i\leq 2\cdot 10^5

subtask3(40),无特殊限制。

时间限制:1s\texttt{1s}

空间限制:512M\texttt{512M}