Problem:


Score : 600 points

Problem Statement

There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}.
Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.

Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}.
For Takahashi, find the minimum possible total cost to achieve the objective.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq D \leq 10^9

1 \leq A_{i} \leq 10^9

A_{i} and D are integers.

Input

Input is given from Standard Input in the following format:

N D
A_1 A_2 ... A_N

Output

Print the minimum possible total cost.

Sample Input 1

3 1
1 100 1

Sample Output 1

106

This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.

Sample Input 2

3 1000
1 100 1

Sample Output 2

2202

Sample Input 3

6 14
25 171 7 1 17 162

Sample Output 3

497

Sample Input 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

Sample Output 4

658



Sample input:
3 1
1 100 1


Sample output:
106

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L < R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                #self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    edge_append = edge.append
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            i_ori = val2idx_plus[val_plus]
            if i > i_ori:
                val2idx_plus[val_plus] = i
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            i_ori = val2idx_minus[val_minus]
            if i < i_ori:
                val2idx_minus[val_minus] = i   
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L < R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                #self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    edge_append = edge.append
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            val2idx_plus[val_plus] = max(i, val2idx_plus[val_plus])
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            val2idx_minus[val_minus] = min(i, val2idx_minus[val_minus])
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) >> 1
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    edge_append = edge.append
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            val2idx_plus[val_plus] = max(i, val2idx_plus[val_plus])
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            val2idx_minus[val_minus] = min(i, val2idx_minus[val_minus])
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) // 2
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first // 2
                last = last // 2 - 1
            return ret

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = []
    for i, a in enumerate(A):
        tmp.append((a, i+1))
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            val2idx_plus[val_plus] = max(i, val2idx_plus[val_plus])
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            val2idx_minus[val_minus] = min(i, val2idx_minus[val_minus])
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            edge.append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            edge.append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    cnt = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
        cnt += 1
        if cnt == N-1:
            break
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) // 2
                self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret = min(ret, self.seg_min[last])
                first = first // 2
                last = last // 2 - 1
            return ret

    N, D = map(int, input().split())
    A = list(map(int, input().split()))

    tmp = []
    for i, a in enumerate(A):
        tmp.append((a, i+1))
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            val2idx_plus[val_plus] = max(i, val2idx_plus[val_plus])
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            val2idx_minus[val_minus] = min(i, val2idx_minus[val_minus])
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            edge.append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            edge.append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
import sys
input = sys.stdin.readline
def solve():
  n,d = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  D = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(i+1,n):
      D[i][j] = abs(i-j)*d+a[i]+a[j]
  D = minimum_spanning_tree(D)
  print(int(D.sum()))
solve()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
def solve():
  n,d = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  D = [[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      if not i == j:
        D[i][j] = abs(i-j)*d+a[i]+a[j]
  D = minimum_spanning_tree(D)
  print(int(D.sum()))
solve()

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
import heapq
INF = float("inf")
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###

N, D = mi()

#As[i] = [各都市のコスト,各都市の番号]
#0-indexed
As = [[a, i] for i, a in enumerate(list(mi()))]

#Union-Find ****0スタートなので注意！****
class UnionFind():
  # 作りたい要素数（ノードの数）nで初期化
  # 使用するインスタンス変数の初期化
  def __init__(self, n):
    self.n = n
    # root[x]<0ならそのノードが根かつその値が木の要素数
    # rootノードでその木の要素数を記録する
    self.root = [-1]*(n) #元々はn+1になっていたが、nにした（n+1なら1スタートで使えるかもしれないが、Count_Trees()がおかしくなるのでやめた）
    # 木をくっつける時にアンバランスにならないように調整する
    self.rnk = [0]*(n) #元々はn+1になっていたが、nにした

  # ノードxのrootノードを見つける
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      # ついでに経路圧縮（調べた辺を根に直接つなぎ直す）をかけておく
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  # 木の併合、入力は併合したい集合に属する各ノード
  def Unite(self, x, y):
    # 入力ノードのrootノードを見つける
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    # すでに同じ木に属していた場合、何もしないで返す
    if(x == y):
      return
    # 違う木に属していた場合rnkを見てくっつける方を決める
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x] += self.root[y] #要素数を足す(根のrootは"-要素数")
      self.root[y] = x #ノードyの親をx（新しい集合の根）とする
      return 1
    else:
      self.root[y] += self.root[x] #要素数を足す
      self.root[x] = y
      # rnkが同じ（深さに差がない場合）は1増やす（根(rnk1)+繋げる集合のrnkということで、1増えることになる）
      if(self.rnk[x] == self.rnk[y]):
          self.rnk[y] += 1
      return 1

  # xとyが同じグループに属するか判断
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  # ノードxが属する木のサイズを返す（根ノードの.root[idx]を-符号を外して返すだけ
  def Count(self, x):
    return -self.root[self.Find_Root(x)] #-符号を外す

#As_規模降順 = [各都市の規模, 各都市の番号（降順ソート前の番号）]
from operator import itemgetter
As_costdescending = sorted(As, key=itemgetter(0), reverse=True)

#やっぱSegTree使う
seg_length = N
bitlen = (seg_length-1).bit_length() #number of raws except 1st row
N0 = 2**bitlen #length of lowest 
#INF = 2**31-1 #自分のtemplateで宣言してるのでいらない
data = [[INF,0] for _ in range(2*N0)]
#各ノードにおける最小値のidxの初期値を格納
for i in range(1, bitlen+1): #(0は除き)1,2,3段目に行う iは段数を表す
  for j in range(0,2**i): #一番左は0のまま、残りはidxを変える
    #i段目の左端のidxは2**i-1
    data[2**i-1 + j][1] = (2**(bitlen-i))*j
#receive arr and initialize segtree
#not necessarily needed
def segfy(arr):
  i = 0
  for val in arr: #update lowest
    data[i+N0-1][0] = val
    i += 1
  #i is row number
  for i in range(bitlen-1, -1, -1):
    k = 2**i - 1 #idx
    for j in range(0,2**i):
      if data[2*k+1][0]<=data[2*k+2][0]:
    	  data[k] = [data[2*k+1][0],data[2*k+1][1]]
      else:
    	  data[k] = [data[2*k+2][0],data[2*k+2][1]]
      k += 1
# a_k の値を x に更新
def update(k, x):
  firstk = k
  k += N0-1 #この時のk : セグ木上の最下段のidx
  data[k][0] = x
  while k >= 0:
#    print('最初はkは',firstk, 'でしたが今は', k, x, k+N0-1)
    k = (k - 1) // 2
    left = data[2*k+1][0]
    right = data[2*k+2][0]
    if left <= right: #左側が小さければ親ノードに左に入っているidxを送る
      data[k][1] = data[2*k+1][1]
    else: data[k][1] = data[2*k+2][1] #右側が小さかったら
    data[k][0] = min(left,right)
    #右隣のノードと比べて、上のノードに最小値を返す？
# 区間[l, r)の最小値
def query(l, r):
  L = l + N0; R = r + N0
  s = INF
  minidx = 0
  while L < R:
    if R & 1:
      R -= 1
      if data[R-1][0]<s:
        minidx = data[R-1][1]
        s = data[R-1][0]

    if L & 1:
      if data[L-1][0]<s:
        minidx = data[L-1][1]
        s = data[L-1][0]
      L += 1
    L >>= 1; R >>= 1
  return s, minidx
#SegTreeおわり

#もう一個セグ木をつくる（力技）
data2 = [[INF,0] for _ in range(2*N0)]
#各ノードにおける最小値のidxの初期値を格納
for i in range(1, bitlen+1): #(0は除き)1,2,3段目に行う iは段数を表す
  for j in range(0,2**i):
    #一番左は0のまま、残りはidxを変える
    #i段目の左端のidxは2**i-1
    data2[2**i-1 + j][1] = (2**(bitlen-i))*j
#receive arr and initialize segtree
#not necessarily needed
def segfy_(arr):
  i = 0
  for val in arr: #update lowest
    data2[i+N0-1][0] = val
    i += 1
  #i is row number
  for i in range(bitlen-1, -1, -1):
    k = 2**i - 1 #idx
    for j in range(0,2**i):
      if data2[2*k+1][0]<=data2[2*k+2][0]:
    	  data2[k] = [data2[2*k+1][0],data2[2*k+1][1]]
      else:
    	  data2[k] = [data2[2*k+2][0],data2[2*k+2][1]]
      k += 1
# a_k の値を x に更新
def update_(k, x):
  firstk = k
  k += N0-1 #この時のk : セグ木上の最下段のidx
  data2[k][0] = x
  while k >= 0:
#    print('最初はkは',firstk, 'でしたが今は', k, x, k+N0-1)
    k = (k - 1) // 2
    left = data2[2*k+1][0]
    right = data2[2*k+2][0]
    if left <= right: #左側が小さければ親ノードに左に入っているidxを送る
      data2[k][1] = data2[2*k+1][1]
    else: data2[k][1] = data2[2*k+2][1] #右側が小さかったら
    data2[k][0] = min(left,right)
    #右隣のノードと比べて、上のノードに最小値を返す？
# 区間[l, r)の最小値
def query_(l, r):
  L = l + N0; R = r + N0
  s = INF
  minidx = 0
  while L < R:
    if R & 1:
      R -= 1
      if data2[R-1][0]<s:
        minidx = data2[R-1][1]
        s = data2[R-1][0]

    if L & 1:
      if data2[L-1][0]<s:
        minidx = data2[L-1][1]
        s = data2[L-1][0]
      L += 1
    L >>= 1; R >>= 1
  return s, minidx
#SegTree_おわり

aforseg =[]
aforseg_ =[]
for a, i in As:
  aforseg.append((N-1-i)*D+a)
  aforseg_.append(i*D+a)

segfy(aforseg)
segfy_(aforseg_)
#print(data)
#print(data2)

#print(cummin_left)
#print(cummin_right)
#[(cost, idx, adjidx), ...]
edge_candidates = []

for a, o_idx in As_costdescending: #o_idx:降順にする前のidx
  if o_idx == 0: #右だけを見る
    rightmin, rightmin_oidx = query_(1,N) #[L,r)
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+rightmin-rightmin_oidx*D, o_idx, rightmin_oidx))
  elif o_idx == N-1: #左だけを見る
    leftmin, leftmin_oidx = query(0, N-1) #[L,r)
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+leftmin-(N-1-leftmin_oidx)*D, o_idx, leftmin_oidx))
  else:
    rightmin, rightmin_oidx = query_(o_idx+1,N) #[L,r)
    edge_candidates.append((abs(o_idx-rightmin_oidx)*D+a+rightmin-rightmin_oidx*D, o_idx, rightmin_oidx))
    leftmin, leftmin_oidx = query(0, o_idx) #[L,r)
    edge_candidates.append((abs(o_idx-leftmin_oidx)*D+a+leftmin-(N-1-leftmin_oidx)*D, o_idx, leftmin_oidx))
  update(o_idx,INF)
  update_(o_idx,INF)

heapq.heapify(edge_candidates)

#上でできた配列に対してクラスカル法を適用して最小全域木（のコスト総和）を求める
#Union-Findを使ったクラスカル法
uf = UnionFind(N)
ans = 0
for _ in range(len(edge_candidates)):
  c, idx, adjidx = heapq.heappop(edge_candidates)
  if uf.Unite(idx, adjidx): ans += c

print(ans)