Sau khi tham gia kỳ thi chọn học sinh giỏi cấp tỉnh lớp 11, Zin tự thưởng cho mình bằng việc tham gia một trò chơi điện tử. Trò chơi có tất cả ~n~ nhiệm vụ, mỗi nhiệm vụ cần phải tiêu tốn ~d~ đơn vị thời gian liên tiếp để hoàn thành. Các nhiệm vụ được đánh số từ ~1~ đến ~n~. Nếu thực hiện nhiệm vụ thứ ~i~, Zin sẽ nhận được điểm thưởng là ~z_i~. Biết rằng, từ thời điểm ~0~ tất cả các nhiệm vụ đều sẵn sàng cho Zin lựa chọn để thực hiện và sau thời điểm ~t_i~ nhiệm vụ thứ ~i~ sẽ bị hủy.

Yêu cầu: Hãy giúp Zin chọn ra các nhiệm vụ để thực hiện sao cho sau khi kết thúc trò chơi số điểm thưởng nhận được là lớn nhất.

Input

• Dòng 1: Chứa hai số nguyên dương ~n~ và ~d~ ~(1 \le n \le 10^5; 1 \le d \le 10^9)~;

• Dòng 2: Chứa ~n~ số nguyên dương ~t_1,t_2,\dots,t_n~ ~(1 \le t_i \le 10^9; 1 \le i \le n)~;

• Dòng 3: Chứa ~n~ số nguyên dương ~z_1,z_2,\dots,z_n~ ~(1 \le z_i \le 10^9; 1 \le i \le n)~.

Output

Ghi ra một số nguyên duy nhất là tổng điểm thưởng lớn nhất mà Zin có thể thu được.

Scoring

Sample Input 1

5 2
4 3 2 7 6
3 5 3 2 1

Sample Output 1

10

Notes

Các nhiệm vụ mà Zin chọn có thứ tự là: ~2; 1; 4~.

Tổng điểm thưởng là: ~5 + 3 + 2 = 10~.