Moving the Light Stone

At the center of the kingdom of Polymath stands the Light Stone, which supplies light to the people. The Light Stone can supply light to places up to a distance $L$ away. Because the Light Stone is growing weaker, the people want to move it so that every house can be supplied with light.

The destination of the Light Stone is already decided. The problem is that moving the Light Stone costs a lot. To minimize the cost, they must decide for each part of the way whether to drag the Light Stone or carry it.

Divide the route over which the Light Stone is moved into $N$ segments. In segment $i$, dragging the Light Stone costs $A_i$, and carrying it costs $B_i$. Also, each time the way of moving the Light Stone changes, an extra cost $K$ is incurred. (There is no extra cost $K$ at the very beginning or the very end.)

For example, let $N=3$, $K=2$, $A=[1, 7, 3]$, $B=[9, 3, 4]$. Dragging the stone over the entire route costs $1+7+3=11$. On the other hand, dragging it in the first segment and carrying it in the second and third segments costs $1+2+3+4=10$, so the stone can be moved for less.

The first line gives the number of segments $N$ and the cost $K$ of changing the way of moving.

The second line gives the costs $A_1, A_2, \cdots, A_N$ of dragging the Light Stone.

The third line gives the costs $B_1, B_2, \cdots, B_N$ of carrying the Light Stone.

Print the minimum cost of moving the Light Stone.

• $1 \le N \le 2 \times 10^5$
• $0 \le K \le 10^9$
• $1 \le A_i, B_i \le 10^9$