VNOI Marathon 08

Với một số tự nhiên được viết trong hệ cơ số 10, ta định nghĩa vị trí xấu là vị trí mà chữ số tại đó với chữ số kề sau nó có độ chênh lệch không quá D. Nếu một số có không quá K vị trí xấu thì đó là số đẹp.

Hãy đếm số lượng số đẹp trong khoảng từ A đến B.

Dữ liệu

Gồm một dòng duy nhất là 4 số A, B, D, K.

Kết quả

Gồm một dòng duy nhất là số lượng số đếm được.

Giới hạn

1 ≤ A ≤ B ≤ 10¹⁵

Ví dụ

Dữ liệu
1 13 1 0

Kết quả
10