Bessie, cô bò lúc nào cũng gây rắc rối, đã lấy trộm máy kéo của Farmer John rồi phóng đi trên đường!

Con đường dài đúng 100 dặm và Bessie lái hết chiều dài con đường trước khi cuối cùng bị một cảnh sát yêu cầu dừng xe. Viên cảnh sát phạt Bessie vì chạy quá tốc độ, sử dụng giấy phép đã hết hạn và điều khiển một phương tiện cơ giới trong khi là bò. Bessie thừa nhận rằng hai lỗi sau có lẽ là đúng, nhưng cô nghi ngờ liệu viên cảnh sát có đúng khi phạt lỗi chạy quá tốc độ hay không. Cô muốn tự mình xác định xem trong một phần hành trình, mình có thực sự lái nhanh hơn giới hạn tốc độ hay không.

Con đường được chia thành \(N\) đoạn. Mỗi đoạn được mô tả bởi một số nguyên dương là chiều dài tính bằng dặm và một số nguyên là giới hạn tốc độ trong đoạn \(1\ldots100\) dặm một giờ. Vì con đường dài 100 dặm nên tổng chiều dài của tất cả \(N\) đoạn bằng 100. Ví dụ, con đường có thể bắt đầu bằng một đoạn dài 45 dặm với giới hạn tốc độ 70, rồi kết thúc bằng một đoạn dài 55 dặm với giới hạn tốc độ 60.

Hành trình của Bessie cũng có thể được mô tả bằng \(M\) đoạn. Trong mỗi đoạn, cô đi một số nguyên dương dặm nhất định với một tốc độ nguyên nhất định. Ví dụ, cô có thể bắt đầu bằng việc đi 50 dặm với tốc độ 65, sau đó đi thêm 50 dặm với tốc độ 55. Tổng chiều dài của tất cả \(M\) đoạn bằng 100 dặm. Máy kéo của Farmer John có thể chạy nhanh nhất 100 dặm một giờ.

Với các thông tin trên, hãy xác định mức vượt quá giới hạn tốc độ lớn nhất của Bessie tại bất kỳ phần nào trong hành trình.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi dấu cách.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một đoạn đường: chiều dài và giới hạn tốc độ của đoạn đó.

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên mô tả một đoạn trong hành trình của Bessie: chiều dài đoạn và tốc độ mà Bessie đã lái.

Dữ liệu ra

In một dòng chứa mức vượt quá giới hạn tốc độ lớn nhất của Bessie tại bất kỳ phần nào trong hành trình. Nếu cô không bao giờ vượt quá giới hạn tốc độ, hãy in 0.

Ví dụ

3 3
40 75
50 35
10 45
40 76
20 30
40 40

5

Nguồn

USACO 2015 December Contest, Bronze - Speeding Ticket: https://usaco.org/index.php?page=viewproblem2&cpid=568

Tác giả: Austin Bannister và Brian Dean.