Một công ty công nghệ có một quy trình xử lý dữ liệu gồm ~N~ bước tuần tự. Họ sở hữu ~2~ cụm máy chủ: Cụm ~A~ và Cụm ~B~.

• Nếu chạy bước thứ ~i~ trên Cụm ~A~, mất thời gian là ~A_i~ mili-giây.

• Nếu chạy bước thứ ~i~ trên Cụm ~B~, mất thời gian là ~B_i~ mili-giây.

Dữ liệu có thể được chuyển qua lại giữa ~2~ cụm máy chủ giữa các bước. Tuy nhiên, mỗi lần chuyển đổi từ cụm ~A~ sang cụm ~B~ hoặc ngược lại sẽ tiêu tốn một khoảng thời gian trễ là ~C~ mili-giây. Bước đầu tiên có thể bắt đầu ở bất kỳ cụm nào mà không tốn phí chuyển đổi ban đầu.

Yêu cầu: Tìm thời gian tối thiểu để hoàn thành toàn bộ ~N~ bước.

Input

• Dòng ~1~: Hai số nguyên dương ~N~ và ~C~ ~(1 \le N \le 10^5, 1 \le C \le 10^6)~.

• Dòng ~2~: ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ ~(1 \le A_i \le 10^6)~.

• Dòng ~3~: ~N~ số nguyên dương ~B_1, B_2, \dots, B_N~ ~(1 \le B_i \le 10^6)~.

Output

Thời gian tối thiểu để hoàn thành ~N~ bước.

Scoring

Sample Input 1

4 10
5 20 5 25
30 4 30 6

Sample Output 1

46

Sample Input 2

3 2
10 1 10
1 10 1

Sample Output 2

7

Notes

Với ví dụ thứ nhất, để đạt tổng thời gian ~46~, ta chạy như sau:

• Bước ~1, 2~ và ~3~ chạy trên Cụm ~A~: Tốn ~5 + 20 + 5 = 30~.

• Trước khi làm Bước ~4~, chuyển dữ liệu sang Cụm ~B~: Tốn phí chuyển đổi là ~10~.

• Bước ~4~ chạy trên Cụm ~B~: Tốn ~6~.

Tổng cộng: ~30 + 10 + 6 = 46~.

Với ví dụ thứ hai, chi phí chuyển đổi mạng giữa ~2~ cụm là ~C = 2~, nên ta có thể chuyển liên tục để chọn máy chủ nhanh nhất:

• Bước ~1~: Bắt đầu ngay tại Cụm ~B~ (tốn ~1~).

• Bước ~2~: Chuyển sang ~A~ (tốn ~2~) và chạy trên ~A~ (tốn ~1~).

• Bước ~3~: Chuyển về ~B~ (tốn ~2~) và chạy trên ~B~ (tốn ~1~).

Tổng cộng: ~1 + 2 + 1 + 2 + 1 = 7~.