Штраф за перевищення швидкості
Бесі, яка завжди створює проблеми, вкрала трактор Фермера Джона і помчала вниз по дорозі! Дорога має довжину рівно 100 миль, і Бесі їде по ній, поки її не зупинить офіцер поліції і не вручить їй квитанцію за перевищення швидкості.
Дорога поділена на n ділянок, кожна з яких має певну позитивну довжину в милях і обмеження швидкості, яке є цілим числом у діапазоні від 1 до 100 миль на годину. Оскільки довжина дороги становить 100 миль, сумарна довжина всіх n ділянок дорівнює 100. Наприклад, дорога може починатися з ділянки довжиною 45 миль з обмеженням швидкості 70 миль на годину, а потім продовжуватися ділянкою довжиною 55 миль з обмеженням швидкості 60 миль на годину.
Рух Бесі також описується серією ділянок — їх m. На кожній ділянці вона проїжджає певну кількість миль з певною цілою швидкістю. Наприклад, вона може їхати 50 миль зі швидкістю 65, а потім 50 миль зі швидкістю 55. Сумарна довжина всіх цих m ділянок також дорівнює 100. Трактор Фермера Джона може рухатися зі швидкістю не більше 100 миль на годину.
Виходячи з цієї інформації, визначте максимальне перевищення швидкості, яке допустила Бесі під час подорожі.
Вхідні дані
Перший рядок містить n і m. Кожен з наступних n рядків містить два цілих числа, що описують ділянку дороги: її довжину і обмеження швидкості.
Кожен з наступних m рядків містить два цілих числа, що описують ділянку подорожі Бесі: її довжину і швидкість, з якою рухалася Бесі.
Вихідні дані
Виведіть один рядок, що містить максимальне перевищення обмеження швидкості, яке допустила Бесі. Якщо вона ніколи не перевищила швидкість, виведіть 0.
Приклад
У цьому прикладі дорога складається з трьох ділянок (40 миль зі швидкісним обмеженням 75 миль на годину, потім 50 миль зі швидкісним обмеженням 35 миль на годину, потім 10 миль зі швидкісним обмеженням 45 миль на годину). Рух Бесі задається трьома ділянками (40 миль зі швидкістю 76 миль на годину, потім 20 миль зі швидкістю 30 миль на годину, потім 40 миль зі швидкістю 40 миль на годину). Протягом першої ділянки вона трохи перевищила швидкість, а на останній ділянці вона перевищила швидкість на 5. Тому відповідь 5.