Mưa Và Những Chiếc Ô

Một người đang ở điểm $x=0$ trên trục số và cần đi tới nhà bạn ở điểm $x=a$. Người đó chỉ di chuyển từ trái sang phải, mỗi giây đi được đúng một đơn vị độ dài.

Trời đang mưa trên $n$ đoạn rời nhau, đoạn thứ $i$ là $[l_i,r_i]$. Trên đường có $m$ chiếc ô, chiếc thứ $i$ nằm ở điểm $x_i$ và có khối lượng $p_i$. Lúc xuất phát người đó không cầm chiếc ô nào.

Trong suốt hành trình, người đó có thể nhặt ô lên hoặc vứt ô xuống tại điểm đang đứng, thao tác này tức thời và có thể cầm bao nhiêu ô tùy ý cùng lúc. Vì không muốn bị ướt, khi đi từ $x$ sang $x+1$ mà đoạn $[x,x+1]$ nằm trong vùng mưa thì người đó phải đang cầm ít nhất một chiếc ô.

Đó là ràng buộc duy nhất. Chẳng hạn, có thể đi tay không tới đúng điểm bắt đầu một đoạn mưa rồi mới nhặt chiếc ô nằm ở đó lên, hoặc đổi ô cho nhau ngay giữa vùng mưa. Lưu ý chiếc ô bị vứt xuống sẽ nằm lại tại điểm đó, mà người đó thì không bao giờ quay lại.

Mỗi đơn vị độ dài đi được làm độ mệt tăng thêm một lượng bằng tổng khối lượng các chiếc ô đang cầm khi di chuyển.

Hãy xác định người đó có thể đi từ $x=0$ tới $x=a$ hay không. Nếu có, hãy tìm độ mệt nhỏ nhất khi tới đích, giả sử việc nhặt và vứt ô được thực hiện tối ưu.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $a$, $n$, $m$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i$ và $r_i$ là hai đầu mút của đoạn mưa thứ $i$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $x_i$ và $p_i$ là vị trí và khối lượng của chiếc ô thứ $i$.

Dữ liệu ra

In ra $-1$ nếu không thể đi từ $x=0$ tới $x=a$. Ngược lại in ra một số nguyên là độ mệt nhỏ nhất khi tới đích.

Ràng buộc

• $1\le a,m\le 2000$
• $1\le n\le \lceil a/2\rceil$
• $0\le l_i<r_i\le a$, các đoạn mưa đôi một không giao nhau
• $0\le x_i\le a$, $1\le p_i\le {10}^5$

Ví dụ