{"problem":{"name":"Connecting Cities","description":{"content":"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","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"keyence2019_e"},"statements":[{"statement_type":"Markdown","content":"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.\nAssume 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.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq D \\leq 10^9$\n*   $1 \\leq A_{i} \\leq 10^9$\n*   $A_{i}$ and $D$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $D$\n$A_1$ $A_2$ $...$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"keyence2019_e","tags":[],"sample_group":[["3 1\n1 100 1","106\n\nThis cost can be achieved by, for example, building roads connecting City $1$, $2$ and City $1$, $3$."],["3 1000\n1 100 1","2202"],["6 14\n25 171 7 1 17 162","497"],["12 5\n43 94 27 3 69 99 56 25 8 15 46 8","658"]],"created_at":"2026-03-03 11:01:14"}}