Vương quốc IT có một giải đua xe mà phần thưởng chỉ trao cho người lái xe đi xa nhất có thể. Giải đua như sau: ban đầu mỗi một chiếc xe được bơm vào bình một lượng xăng chỉ đủ để đi một quãng đường là ~s~ km và được cấp một số tiền là ~k~ coin (đơn vị tiền tệ của vương quốc IT). Trên đường đua, điểm xuất phát được bố trí ở vị trí 0 km và có ~n~ trạm tiếp xăng. Trạm tiếp xăng thứ ~i~ ở km ~x_i~ và bơm cho xe vào bình lượng xăng có thể đi thêm được ~a_i~ km với chi phí là 1 coin.

Yêu cầu: Cho biết ~s~, ~k~, ~n~, vị trí ~x_i~ và ~a_i~ (của trạm xăng thứ ~i~), hãy xác định quãng đường xa nhất mà xe đua có thể đi được.

Dữ liệu

• Dòng đầu chứa 3 số nguyên dương ~s, k, n~ (~s \le 10^5~, ~k \le 10^5~, ~n \le 10^5~, ~k \le n~);
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa 2 số nguyên dương ~x_i~ và ~a_i~ (~x_i \le 10^5~; ~a_i \le 10^3~).

Kết quả

Ghi ra quãng đường xa nhất mà xe đua có thể đi được.

Ví dụ

CAU6.INP

4 3 7
1 2
2 5
7 1
3 3
5 1
4 1
6 2

CAU6.OUT

14

Giới hạn

• Có 50% số test ứng với 50% số điểm của bài thỏa mãn điều kiện ~1 \le n \le 10^3~;
• Có 50% số test còn lại ứng với 50% số điểm của bài thỏa mãn điều kiện ~10^3 < n \le 10^5~.