Trên một con đường thẳng có nhà của chủ tịch K và cựu chủ tịch M của JOI. Chú koala IOI dự định nhảy từ nhà chủ tịch K đến nhà cựu chủ tịch M.

Xem con đường là một trục số. Hai ngôi nhà có tọa độ lần lượt là \(K\) và \(M\). Giữa chúng có \(N\) ngôi nhà của các trợ giảng JOI; nhà của trợ giảng thứ \(i\) có tọa độ \(T_i\).

IOI xuất phát tại tọa độ \(K\) với thể lực bằng \(0\). Trong mỗi lần nhảy, IOI tiến về phía nhà ở tọa độ \(M\) một khoảng cách nguyên \(d\) thỏa mãn \(1 \le d \le D\). Mỗi lần nhảy làm thể lực giảm \(A\); thể lực được phép âm.

Nếu đáp xuống đúng vị trí nhà của một trợ giảng, IOI có thể nghỉ lại tại đó một lần. Nghỉ tại nhà của trợ giảng thứ \(i\) làm thể lực tăng \(B_i\). IOI muốn đến đúng tọa độ \(M\) với thể lực lớn nhất có thể.

Yêu cầu

Tính giá trị thể lực lớn nhất IOI có thể có khi đến nhà ở tọa độ \(M\).

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa năm số nguyên \(K,M,D,A,N\): tọa độ xuất phát, tọa độ đích, khoảng cách nhảy tối đa, lượng thể lực mất sau mỗi lần nhảy và số nhà trợ giảng.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(T_i,B_i\): tọa độ nhà của trợ giảng thứ \(i\) và lượng thể lực nhận được khi nghỉ tại đó.

Các số trên cùng một dòng được phân cách bằng dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: thể lực lớn nhất có thể có khi IOI đến tọa độ \(M\).

Giới hạn

• \(1 \le D \le 1\,000\,000\,000\).
• \(1 \le A \le 1\,000\,000\,000\).
• \(1 \le N \le 100\,000\).
• \(0 \le K < T_1 < T_2 < \cdots < T_N < M \le 1\,000\,000\,000\).
• \(1 \le B_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• Thời gian: 2 giây. Bộ nhớ: 256 MB.

Chấm điểm

Mỗi nhóm kiểm thử gồm một hoặc nhiều bộ dữ liệu. Chỉ nhận được điểm của một nhóm khi chương trình trả lời đúng tất cả bộ dữ liệu trong nhóm và đáp ứng giới hạn thời gian, bộ nhớ.

• Bài toán con 1 (20 điểm): \(N \le 1\,000\).
• Bài toán con 2 (30 điểm): \(D \le 100\).
• Bài toán con 3 (50 điểm): Không có giới hạn bổ sung.

Ví dụ

0 10 4 10 2
3 10
8 5

-20

Một cách di chuyển tối ưu:

• Nhảy \(3\) đơn vị đến tọa độ \(3\), thể lực còn \(-10\).
• Nghỉ tại nhà trợ giảng thứ \(1\), thể lực trở thành \(0\).
• Nhảy \(4\) đơn vị đến tọa độ \(7\), thể lực còn \(-10\).
• Nhảy \(3\) đơn vị đến tọa độ \(10\), thể lực còn \(-20\).

3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10

-25

Một cách di chuyển tối ưu:

• Nhảy \(9\) đơn vị đến tọa độ \(12\), thể lực còn \(-10\).
• Nghỉ tại nhà trợ giảng thứ \(2\), thể lực trở thành \(-1\).
• Nhảy \(9\) đơn vị đến tọa độ \(21\), thể lực còn \(-11\).
• Nhảy \(9\) đơn vị đến tọa độ \(30\), thể lực còn \(-21\).
• Nghỉ tại nhà trợ giảng thứ \(5\), thể lực trở thành \(-13\).
• Nhảy \(6\) đơn vị đến tọa độ \(36\), thể lực còn \(-23\).
• Nghỉ tại nhà trợ giảng thứ \(7\), thể lực trở thành \(-15\).
• Nhảy \(6\) đơn vị đến tọa độ \(42\), thể lực còn \(-25\).