Cho dãy gồm \(N\) điểm trên một trục số. Điểm thứ \(i\) nằm ở tọa độ \(X_i\) và có trọng số \(W_i\). Các điểm được sắp xếp theo thứ tự tăng dần của tọa độ (\(X_1 < X_2 < \dots < X_N\)).

Nhiệm vụ của bạn là chọn ra một dãy con các điểm ở các chỉ số \(i_1 < i_2 < \dots < i_m\) (\(m \ge 1\)) sao cho thỏa mãn đồng thời hai điều kiện sau:

1. Khoảng cách tọa độ giữa hai điểm liên tiếp được chọn ít nhất là \(D\):

1. Chênh lệch trị tuyệt đối trọng số giữa hai điểm liên tiếp được chọn tối đa là \(K\):

Hãy tìm tổng trọng số lớn nhất có thể đạt được: \(\sum_{s=1}^m W_{i_s}\). Chú ý rằng các trọng số có thể âm, và bạn luôn phải chọn ít nhất một điểm (\(m \ge 1\)).

Input

• Dòng đầu tiên chứa ba số nguyên \(N, D, K\) (\(1 \le N \le 10^5\), \(0 \le D, K \le 10^9\)).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(X_i, W_i\) (\(1 \le X_i \le 10^9\), \(-10^9 \le W_i \le 10^9\)). Dữ liệu đảm bảo \(X_1 < X_2 < \dots < X_N\).

Output

• In ra một số nguyên duy nhất là tổng trọng số lớn nhất đạt được của dãy con hợp lệ.

Chấm điểm

• Subtask duy nhất (100 điểm): Không có ràng buộc gì thêm.

Ví dụ

4 3 5
1 10
3 -5
5 12
8 7

29