Trong lớp học có ~N~ bạn, điểm của bạn thứ ~i~ gọi là ~a_{i}~. Nhận thấy sự chênh lệch giữa các bạn trong lớp, cô giáo đã đưa ra khẩu hiệu "Chúng ta cùng tiến" nhằm cải thiện khả năng và điểm số của mỗi bạn.

Cụ thể, cô đã chia lớp thành nhiều nhóm, mỗi nhóm đều phải thỏa điều kiện: Khi sắp xếp điểm số của các bạn trong nhóm tăng dần, thì chênh lệch điểm số giữa hai bạn liên tiếp không được lớn hơn giá trị ~D~ mà cô giáo đã cho.

Ví dụ:

• Nếu ~D = 3~, và điểm của một nhóm nào đó là ~[5, 2, 1, 7, 5]~, thì nhóm này hợp lệ (Vì khi sắp xếp lại ta sẽ được ~[1, 2, 5, 5, 7]~, và chênh lệch của giữa các bạn là: ~3 - 1 \leq D~, ~5 - 2 \leq D~, ~5 - 5 \leq D~, ~7 -5 \leq D~ ).
• Nếu ~D = 5~, và điểm của một nhóm nào đó là ~[6, 2, 15, 17]~, thì nhóm này không hợp lệ (Vì khi sắp xếp lại ta sẽ được ~[2, 6, 15, 17]~, và dễ dàng thấy được ~15 - 6 > D~, không thỏa yêu cầu).

Bên cạnh ~N~ bạn trong lớp, cô giáo sẽ cho thêm tối đa ~M~ bạn (với điểm số bất kì) nhằm giảm số lượng nhóm hiện có. Là một học sinh giỏi, bạn hãy giúp cô chia tất cả các bạn trong lớp vào các nhóm sao cho số lượng nhóm là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên gồm ba số nguyên ~N, M, D~ ~(1 \leq N \leq 2 \times 10^5, 1 \leq M, D \leq 10^{18})~ - lần lượt là số học sinh trong lớp, số học sinh tối đa được thêm vào, và chênh lệch điểm tối đa mà cô giáo đưa ra.
• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \leq a_i \leq 10^{18})~ là điểm số của từng học sinh trong lớp.

Kết quả ra

• Gồm một số nguyên duy nhất là số lượng nhóm nhỏ nhất tìm được.

Ràng buộc

• Subtask ~1~ ~(15 \%)~: ~1 \leq N \leq 8, M = 0~.
• Subtask ~2~ ~(25 \%)~: ~M = 0~.
• Subtask ~3~ ~(60 \%)~: Không có ràng buộc gì thêm.

Ví dụ 1

Dữ liệu vào

4 2 5
1 3 15 21

Kết quả ra

2

Giải thích

Có hai cách chia như sau:

• Có thể thêm một bạn học sinh với điểm số là ~16~ và sẽ chia được hai nhóm: ~[1, 3]~ và ~[15, 16, 21]~.
• Có thể thêm hai bạn với điểm số lần lượt là ~8~ và ~13~ và sẽ chia được hai nhóm: ~[1, 3, 8, 13, 15]~ và ~[21]~.

Ví dụ 2

Dữ liệu vào

3 1 2
1 6 8

Kết quả ra

2

Giải thích

• Không có cách thêm học sinh để giảm số lượng nhóm, nên chia được hai nhóm là: ~[1]~ và ~[6, 8]~.

Ví dụ 3

Dữ liệu vào

5 2 2
10 1 45 6 48

Kết quả ra

3

Giải thích

• Có thể thêm hai bạn với điểm số lần lượt là ~8~ và ~46~ và sẽ chia được ba nhóm: ~[1]~, ~[6, 8, 10]~ và ~[45, 46, 48]~.