Беси, которая всегда создаёт проблемы, украла трактор Фермера Джона
и помчалась вниз по дороге!
Дорога имеет длину ровно 100 миль и Беси едет по ней, пока
её не остановит офицер полиции и не вручит ей квитанцию о превышении
скорости.
Дорога поделена на \(N\) участков, каждый описывается положительной
длиной в милях, а также целым числом - пределом скорости на этом участке,
в диапазоне \(1 \ldots 100\) миль в час. Поскольку длина дороги 100 миль,
суммарная длина всех \(N\) участков равна 100. Например, дорога может начаться
участком в 45 миль со скоростным пределом 70 миль в час, и затем будет участок в 55 миль,
со скоростным пределом 60 миль в час.
Движение Беси тоже может быть описано серией участков - \(M\) штук.
На каждом участке она проезжает определённое количество миль с определённой
целочисленной скоростью. Например, она может ехать 50 миль со скоростью 65,
а затем 50 миль со скоростью 55. Суммарная длина всех этих \(M\) участков также
равна 100. Трактор ФД может двигаться со скоростью не более 100 миль в час.
По заданной выше информации, определите максимальное превышение скорости,
которое допустила Беси во время путешествия.
Формат ввода (файл speeding.in):
Первая строка ввода содержит
\(N\) и
\(M\), разделённые одним пробелом.
Каждая из следующих \(N\) строк содержит два целых числа, описывающих
участок дороги: задавая его длину и предел скорости
Каждая из следующих \(M\) строк содержит два целых числа, описывающих
участок путешествия Беси: задавая его длину и скорость, на которой двигалась Беси.
Формат вывода (файл speeding.out):
Выведите одну строку, содержащую максимальное превышение предела скорости,
которое допустила Беси. Если она никогда не превысила скорость, выведите 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
40 75
50 35
10 45
40 76
20 30
40 40
|
5
|