THPT Chuyên Bến Tre

Vua Hùng tổ chức một cuộc thi tài để kén Phò Mã cho công chúa Mị Nương. Các chàng trai tham dự cuộc thi sẽ phải mang đầy đủ sính lễ đến theo yêu cầu của nhà Vua. Sính lễ bắt buộc phải là n loại linh vật của n ngôi làng trong đất nước. Chàng trai thông minh nhất là người mang đầy đủ sính lễ đến với số tiền bỏ ra là ít nhất và sẽ được kết duyên cùng công chúa Mị Nương.

Vào thời đó, cả nước có tất cả 2n ngôi làng trong đó n ngôi làng nằm bên trái của con sông X, và n ngôi làng còn lại nằm ở bên phải của sông X. Ở hai bên sông, các ngôi làng được đánh số lần lượt từ 1 đến n theo thứ tự từ ngôi làng ở đầu sông đến ngôi làng ở cuối sông. Một ngôi làng chỉ có một loại linh vật. Giả sử không giới hạn số lượng linh vật của từng loại linh vật. Để có được 1 loại linh vật thì các chàng trai phải mua và trả một số tiền bằng giá trị 1 linh vật của loại linh vật đó.

Mỗi chàng trai được chọn nơi xuất phát là ngôi làng có số thứ tự 1 ở một trong hai bờ sông và từ đó đi tiếp tới các ngôi làng khác. Tới ngôi làng nào thì sẽ mua 1 linh vật của ngôi làng đó. Mua xong linh vật ở ngôi làng thứ i rồi thì phải di chuyển tới ngôi làng thứ i+1 ở một trong 2 bờ sông. Ngoài số tiền phải bỏ ra để mua linh vật, người mua phải trả thêm chi phí di chuyển từ ngôi làng này tới ngôi làng khác.

Chi phí di chuyển được tính như sau: Giữa hai ngôi làng liên tiếp trên cùng một bờ sông coi chi phí bằng 0. Giữa hai ngôi làng ở hai bên bờ sông khác nhau thì chi phí là một số nguyên dương M (M không phụ thuộc vào số thứ tự của 2 ngôi làng).

Các chàng trai sau khi mua đủ sính lễ theo yêu cầu thì sẽ mang sính lễ đó dâng lên nhà Vua tại địa điểm đã được quy định trước là ngôi làng thứ n của bờ sông bên phải. Sơn Tinh đang đau đầu suy nghĩ giải bài toán khó này. Bạn là một lập trình viên đang tham dự kỳ thi Olympic Tin học vùng đồng bằng Sông Hồng và duyên hải Bắc Bộ. Bạn hãy giúp Sơn Tinh giải bài toán của Vua Hùng nhé.

Cho N, M và giá trị của các loại linh vật ở hai bên bờ sông.

Yêu cầu: Hãy đưa ra số tiền ít nhất phải trả để có thể mua được N loại linh vật theo yêu cầu của nhà Vua?

Input

Gồm 3 dòng:

• Dòng đầu tiên ghi 2 số  nguyên N, M  (1≤ N ≤ 10⁵, 1≤ M≤ 10⁹)
• Dòng thứ 2 ghi N số nguyên: a₁, a₂, …., a_n theo thứ tự là giá trị N loại linh vật của các ngôi làng từ 1 đến n ở bờ sông bên trái.
• Dòng thứ 3 ghi N số nguyên: b₁, b₂, …., b_n theo thứ tự là giá trị N loại linh vật của các ngôi làng từ 1 đến n ở bờ sông bên phải.
• (0 < a_i, b_i ≤ 10⁹; a_i, b_i Î Z với mọi iÎ[1..n])
• Các số trên cùng 1 dòng cách nhau ít nhất một dấu cách.

Output

• Gồm 1 dòng duy nhất là số tiền ít nhất phải trả để mua N loại linh vật theo yêu cầu của nhà Vua.

Example

Input:
5 6
4 9 18 7 5
15 10 3 24 1

Output:
42

*Giải thích ví dụ: đi từ ngôi làng 1 ở bờ bên trái -> ngôi làng thứ 2 ở bờ trái -> ngôi làng thứ 3 ở bờ phải -> ngôi làng

 thứ 4 ở bờ trái -> ngôi làng thứ 5 của bờ phải.

Tổng chi phí = 4 + 9 + 6 (do đổi bờ) + 3 + 6 (do đổi bờ) + 7 + 6(do đổi bờ) +1 = 42
* Ghi chú: 
30% số test có n≤1000.
30% số test có n≤5000
40% số test có n≤100000