Giao Kiện Hàng

Một chiếc xe tải cần chở một kiện hàng từ điểm $0$ đến điểm $d$ trên trục số. Bình xăng của xe chứa được đúng $n$ lít và ban đầu đầy. Mỗi đơn vị quãng đường đi được tiêu tốn đúng $1$ lít xăng.

Trên đường đi có $m$ trạm xăng. Trạm thứ $i$ nằm tại điểm $x_i$ và bán xăng với giá $p_i$ đô la mỗi lít (số lượng không giới hạn). Xe có thể mua bao nhiêu lít tùy ý tại mỗi trạm, miễn là tổng lượng xăng trong bình không vượt quá $n$ lít.

Hãy tìm chi phí mua xăng ít nhất để xe hoàn thành việc giao hàng. Nếu không có cách nào đưa xe đến điểm $d$, in ra $-1$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $d$, $n$, $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $p_i$: vị trí và giá xăng của trạm thứ $i$. Các vị trí $x_i$ đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên: chi phí ít nhất, hoặc $-1$ nếu không thể hoàn thành.

Ràng buộc

• $1\le n\le d\le {10}^9$
• $1\le m\le 2·{10}^5$
• $1\le x_i\le d-1$
• $1\le p_i\le {10}^6$

Ví dụ