Để cuối cùng giải quyết cuộc tranh cãi dai dẳng về việc ai là con bò chạy nhanh hơn, Bessie và người bạn Elsie quyết định tổ chức một cuộc đua xuyên trang trại.

Hai con bò xuất phát tại cùng một vị trí và bắt đầu chạy cùng một hướng vào cùng một thời điểm. Quá trình chạy của mỗi con bò được mô tả bởi một chuỗi các "chặng", trong mỗi chặng con bò chạy với vận tốc không đổi. Ví dụ, Bessie có thể chạy với vận tốc 5 trong 3 đơn vị thời gian, sau đó chạy với vận tốc 10 trong 6 đơn vị thời gian. Bessie và Elsie đều chạy trong cùng một tổng thời gian.

Hai con bò muốn bạn giúp đếm số lần vị trí dẫn đầu thay đổi trong cuộc đua. Một lần thay đổi vị trí dẫn đầu xảy ra tại thời điểm bò A vượt lên dẫn trước bò B, trong khi ở lần gần nhất có một con bò dẫn đầu thì đó là bò B. Ví dụ, nếu B đang dẫn đầu rồi A vượt lên trước thì đây là một lần thay đổi vị trí dẫn đầu. Nếu B đang dẫn đầu, sau đó A ngang bằng với B trong một khoảng thời gian rồi cuối cùng vượt lên trước thì điều này cũng được tính là một lần thay đổi vị trí dẫn đầu.

Dữ liệu vào

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

\(N\) dòng tiếp theo, mỗi dòng chứa một trong \(N\) chặng chạy của Bessie, được mô tả bởi hai số nguyên: vận tốc của Bessie và khoảng thời gian cô chạy với vận tốc đó. Cả hai số nguyên đều nằm trong khoảng từ 1 đến 1000.

\(M\) dòng tiếp theo, mỗi dòng chứa một trong \(M\) chặng chạy của Elsie, được mô tả bởi hai số nguyên: vận tốc của Elsie và khoảng thời gian cô chạy với vận tốc đó. Cả hai số nguyên đều nằm trong khoảng từ 1 đến 1000.

Dữ liệu ra

In ra số lần vị trí dẫn đầu thay đổi trong cuộc đua.

Ví dụ

4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 9

2

Nguồn

USACO 2013 March Contest, Bronze — Problem 1: Cow Race

Tác giả đề: Brian Dean, 2013.