Double2D và nhphuc là hai đối thủ không đội trời chung trong tựa game AOE (Đế chế). Hiện tại, với nền văn minh có đa dạng loại quân là Hittite, Double2D đang có \(n\) loại quân đánh số từ \(1\) đến \(n\), loại thứ \(i\) có sức mạnh là \(a_i\) và mức độ khó dùng là \(b_i\).

Để đánh bại nhphuc, Double2D sẽ lựa chọn một đoạn con liên tiếp các loại quân để sử dụng. Sức mạnh khi chọn đoạn con liên tiếp từ \(l\) đến \(r\) được tính bằng công thức:

với \(k\) là hằng số cho trước.

Yêu cầu: Hãy giúp Double2D tìm sức mạnh lớn nhất có thể đạt được để chiến đấu với nhphuc.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le k \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) là sức mạnh của các loại quân (\(1 \le a_i \le 10^9\)).
• Dòng thứ ba chứa \(n\) số nguyên dương \(b_1, b_2, \dots, b_n\) là độ khó dùng của các loại quân (\(1 \le b_i \le 10^9\)).

Output

In ra một số nguyên duy nhất: sức mạnh lớn nhất có thể đạt được.

Scoring (Chấm điểm)

Example

input

5 2
4 2 1 5 3
2 10 1 1 2

output

5

Note

Chọn đoạn \([3; 5]\): tổng sức mạnh là \(1 + 5 + 3 = 9\), độ khó lớn nhất là \(\max(1, 1, 2) = 2\), nên sức mạnh là \(9 - 2 \times 2 = 5\). Không có đoạn nào cho kết quả lớn hơn. Ví dụ, đoạn \([4; 5]\) cho \(8 - 2 \times 2 = 4\) và đoạn \([3; 4]\) cho \(6 - 2 \times 1 = 4\).