Nam là một vận động viên quần vợt chuyên nghiệp. Trong một hệ thống thi đấu quần vợt, người ta tổ chức n giải đấu đánh số từ 1 đến n. Giải đấu thứ i được tổ chức vào ngày thứ ai (ngày Ban tổ chức ra quyết định là ngày thứ 1) và mỗi vận động viên tham gia được cộng điểm thưởng là bi.

Để đảm bảo sức khỏe, huấn luyện viên quyết định hai giải đấu mà Nam chọn tham dự phải cách xa nhau ít nhất là k ngày (|ai-aj| ≥ k nếu Nam tham dự cả giải thứ i và giải thứ j).

Bạn hãy giúp Nam chọn lựa các giải thi đấu sao cho tổng số điểm thưởng là nhiều nhất.

Dữ liệu:

• Dòng đầu tiên là hai số nguyên n và k cách nhau một dấu trống (space) (1≤n≤ 10^5,1≤k≤100)
• Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 10^9) là ngày thi đấu của các giải 1, 2,...,n; mỗi số cách nhau một dấu trống (space). Dữ liệu cho đảm bảo a1 < a2 < a3 < ...< an.
• Dòng thứ ba chứa n số nguyên b1, b2, ..., bn (1 ≤ bi ≤ 10^4) là số điểm thưởng của các giải 1, 2, ..., n; mỗi số cách nhau một dấu trống (space).
• Kết quả: Ghi ra Một số nguyên duy nhất là tổng số điểm thưởng lớn nhất mà Nam có thể có được.

Ví dụ: BAI4.INP

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

BAI4.OUT

10

Nguồn

Nguồn

Phép nén của một số nguyên dương K là gán số đó thành số nguyên dương nhỏ nhất mà K không chia hết.

Ví dụ phép nén số của 120 là 7, vì 7 là số nguyên dương nhỏ nhất mà 120 không chia hết.

Độ nén của một số là số lượng phép nén để số đó thành số 2.

Ví dụ 120 ta có:

120→7→2, vậy độ nén của 120 là 2.

Yêu cầu: Cho hai số nguyên dương A,B (2 ≤ A ≤ B ≤ 10^18).

Tính tổng độ nén của các số lớn hơn hoặc bằng A và nhỏ hơn hoặc bằng B.

Ví dụ:

Input

3 7

Output

8

Giải thích VD

• Độ nén của 3 là 1;
• Độ nén của 4 là 2;
• Độ nén của 5 là 1;
• Độ nén của 6 là 3;
• Độ nén của 7 là 1;

Tổng độ nén là: 8

Nguồn