module mod_segment_tree
  implicit none
  integer(8), parameter :: DEFAULT = 100000000000000000_8
  type segment_tree
    integer :: n, p
    integer(8), pointer :: arr(:,:)
  end type segment_tree
  private
  public :: segment_tree, init_segtree, release_segtree
  public :: update, query, DEFAULT
contains
  function op(x,y) result(ret)
    implicit none
    integer(8) :: x(:), y(:), ret(size(x))
    ret = x
    if (x(1).lt.y(1)) return
    ret = y
    return
  end function op
  subroutine init_segtree(st,n)
    implicit none
    type(segment_tree) :: st
    integer, intent(in) :: n
    integer :: p
    p = 1
    do while (p.lt.n)
      p = 2*p
    end do
    st%n = n
    st%p = p
    allocate(st%arr(2*p-1,2))
    st%arr = DEFAULT
    return
  end subroutine init_segtree
  subroutine release_segtree(st)
    implicit none
    type(segment_tree) :: st
    if (associated(st%arr)) deallocate(st%arr)
    return
  end subroutine release_segtree
  subroutine update(st,i,v)
    implicit none
    type(segment_tree) :: st
    integer, intent(in) :: i
    integer(8), intent(in) :: v
    integer :: x
    x = i+st%p-1
    st%arr(x,1) = v
    st%arr(x,2) = int(i,8)
    do while (x.gt.1)
      x = x/2
      st%arr(x,:) = op(st%arr(2*x,:),st%arr(2*x+1,:))
    end do
    return
  end subroutine update
  function query(st,a,b) result(ret)
    type(segment_tree) :: st
    integer, intent(in) :: a, b
    integer :: l, r
    integer(8) :: ret(size(st%arr(1,:)))
    ret = DEFAULT
    l = a+st%p-1
    r = b+st%p-1
    do while (l.le.r)
      if (mod(l,2).eq.1) then
        ret = op(ret,st%arr(l,:))
        l = l+1
      end if
      if (mod(r,2).eq.0) then
        ret = op(ret,st%arr(r,:))
        r = r-1
      end if
      l = l/2
      r = r/2
    end do
    return
  end function query
end module mod_segment_tree
module mod_union_find
  implicit none
  type union_find
    integer :: n
    integer, pointer :: par(:), rnk(:), siz(:)
  end type union_find
  private
  public :: union_find
  public :: init_union_find, release_union_find, find, same, unite, size_of
contains
  subroutine init_union_find(uf,n)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: n
    integer :: i
    uf%n = n
    allocate(uf%par(n),uf%rnk(n),uf%siz(n))
    uf%rnk = 0
    uf%siz = 1
    do i = 1, n
      uf%par(i) = i
    end do
    return
  end subroutine init_union_find
  subroutine release_union_find(uf)
    implicit none
    type(union_find), intent(inout) :: uf
    if (associated(uf%par)) deallocate(uf%par)
    if (associated(uf%rnk)) deallocate(uf%rnk)
    if (associated(uf%siz)) deallocate(uf%siz)
    return
  end subroutine release_union_find
  recursive function find(uf,i) result(j)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    integer :: j
    if (uf%par(i).ne.i) then
      uf%par(i) = find(uf,uf%par(i))
    end if
    j = uf%par(i)
    return
  end function find
  function same(uf,i,j) result(y)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i, j
    logical :: y
    y = find(uf,i).eq.find(uf,j)
  end function same
  subroutine unite(uf,i,j)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i, j
    integer :: x, y
    x = find(uf,i)
    y = find(uf,j)
    if (x.eq.y) return
    if (uf%rnk(x).lt.uf%rnk(y)) then
      uf%par(x) = y
      uf%siz(y) = uf%siz(y)+uf%siz(x)
    else
      uf%par(y) = x
      uf%siz(x) = uf%siz(x)+uf%siz(y)
      if (uf%rnk(x).eq.uf%rnk(y)) uf%rnk(x) = uf%rnk(x)+1
    end if
    return
  end subroutine unite
  function size_of(uf,i) result(s)
    implicit none
    type(union_find), intent(inout) :: uf
    integer, intent(in) :: i
    integer :: s
    s = uf%siz(find(uf,i))
  end function size_of
end module mod_union_find
program connecting_cities
  use mod_segment_tree
  use mod_union_find
  implicit none
  type(segment_tree) :: lst, rst
  type(union_find) :: uf
  integer :: n, i, j, k, u
  integer(8) :: d, a(200000), b(200000,2), e(400000,3), m, t(2)
  a = 0_8
  b = 0_8
  e = 0_8
  read(*,*) n, d
  read(*,*) a(1:n)
  call init_segtree(lst,n)
  call init_segtree(rst,n)
  call init_union_find(uf,n)
  do i = 1, n
    b(i,1) = -a(1)
    b(i,2) = int(i,8)
    call update(lst,i,int(n-i+1,8)*d+a(i))
    call update(rst,i,int(i,8)*d+a(i))
  end do
  call quick_sort(b(1:n,1:2),1)
  u = 0
  do i = 1, n
    j = int(b(i,2))
    t = query(lst,1,j-1)
    if (t(1).ne.DEFAULT) then
      u = u+1
      k = int(t(2))
      e(u,1) = a(j)+a(k)+d*int(abs(j-k),8)
      e(u,2) = int(j,8)
      e(u,3) = int(k,8)
    end if
    t = query(rst,j+1,n)
    if (t(1).ne.DEFAULT) then
      u = u+1
      k = int(t(2))
      e(u,1) = a(j)+a(k)+d*int(abs(j-k),8)
      e(u,2) = int(j,8)
      e(u,3) = int(k,8)
    end if
    call update(lst,j,DEFAULT)
    call update(rst,j,DEFAULT)
  end do
  call quick_sort(e(1:u,1:3),1)
  m = 0_8
  do i = 1, u
    j = int(e(i,2))
    k = int(e(i,3))
    if (same(uf,j,k)) cycle
    m = m+e(i,1)
    call unite(uf,j,k)
  end do
  write(*,'(i0)') m
  call release_segtree(lst)
  call release_segtree(rst)
  call release_union_find(uf)
  stop
contains
  recursive subroutine quick_sort(a,i)
    implicit none
    integer(8), intent(inout) :: a(:,:)
    integer, intent(in) :: i
    integer(8) :: p, c(size(a(1,:)))
    integer :: n, l, r
    n = size(a(:,1))
    l = 1
    r = n
    p = a((l+r)/2,i)+a(l,i)+a(r,i)-max(a((l+r)/2,i),a(l,i),a(r,i))-min(a((l+r)/2,i),a(l,i),a(r,i))
    do
      do while (a(l,i).lt.p)
        l = l+1
      end do
      do while (a(r,i).gt.p)
        r = r-1
      end do
      if (l.ge.r) exit
      c = a(l,:)
      a(l,:) = a(r,:)
      a(r,:) = c
      l = l+1
      r = r-1
    end do
    if (l.gt.2) call quick_sort(a(1:l-1,:),i)
    if (n.gt.r+1) call quick_sort(a(r+1:n,:),i)
    return
  end subroutine quick_sort
end program connecting_cities