21555번 - 빛의 돌 옮기기 서브태스크

문제

폴리매스 왕국의 중앙에 위치해 있는 빛의 돌은 사람들에게 빛을 공급합니다. 빛의 돌은 거리 $L$만큼 떨어진 곳까지 빛을 공급할 수 있습니다. 빛의 돌의 세기가 점점 약해지고 있기 때문에, 사람들은 빛의 돌의 위치를 옮겨서 모든 집에 빛의 돌이 공급될 수 있게 하려고 합니다.

빛의 돌을 옮길 위치는 이미 정해졌습니다. 문제는 빛의 돌을 옮기기 위해 큰 비용이 든다는 것입니다. 비용을 최소화하기 위해 빛의 돌을 끌고 가야 할지, 아니면 들고 가야 할지 정해야 합니다.

빛의 돌을 옮기게 될 길을 $N$개의 구간으로 나누면, $i$번 구간에서 빛의 돌을 끌고 가려면 $A_i$의 비용이 들고, 빛의 돌을 들고 가려면 $B_i$의 비용이 듭니다. 또한, 빛의 돌을 옮기는 방식을 바꿀 때마다 $K$의 추가 비용이 듭니다. (맨 처음과 맨 끝에는 추가 비용 $K$가 들지 않습니다.)

예를 들어, $N=3,ドル $K=2,ドル $A=[1, 7, 3],ドル $B=[9, 3, 4]$라고 합시다. 돌을 옮기는 한 가지 방법은 전체 구간에서 끌고 가는 것으로, 1ドル+7+3=11$의 비용이 필요합니다. 반면 첫 번째 구간에서는 빛의 돌을 끌어서 옮기고, 두세 번째 구간에서는 빛의 돌을 들어서 옮기면, 1ドル+2+3+4=10$의 비용이 필요하므로 더 적은 비용으로 돌을 옮길 수 있습니다.

입력

첫째 줄에는 구간의 개수 $N$과, 이동 방식을 바꿀 때 드는 비용 $K$가 주어집니다.

둘째 줄에는 빛의 돌을 끌고 갈 때 필요한 비용 $A_1, A_2, \cdots, A_N$이 주어집니다.

셋째 줄에는 빛의 돌을 들고 갈 때 필요한 비용 $B_1, B_2, \cdots, B_N$이 주어집니다.

출력

빛의 돌을 옮기는 데 필요한 최소 비용을 출력합니다.

제한

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

서브태스크

힌트