Штраф за перевищення швидкості#11155
Завжди готова влаштувати неприємності, корова Бессі вкрала трактор фермера Джона і вирушила на ньому по дорозі!
Дорога має довжину рівно миль. Бессі проїжджає всю дорогу від початку до кінця, після чого її зупиняє поліцейський. Він виписує Бессі штраф за перевищення швидкості, за прострочені права та за керування транспортним засобом у стані корови. Бессі визнає, що останні два штрафи, ймовірно, цілком заслужені, але сумнівається, що поліцейський правильно виписав штраф за перевищення швидкості. Вона хоче самостійно з'ясувати, чи справді перевищувала встановлену швидкість на якійсь ділянці шляху.
Дорога поділена на ділянок. Для кожної ділянки задана її довжина — додатне ціле число миль — та обмеження швидкості — ціле число від до миль на годину. Оскільки загальна довжина дороги становить миль, довжини всіх ділянок у сумі дорівнюють .
Наприклад, дорога може починатися з ділянки довжиною миль з обмеженням швидкості миль на годину, а потім продовжуватися ділянкою довжиною миль з обмеженням швидкості миль на годину.
Шлях Бессі також складається з ділянок. На кожній ділянці вона проїжджає певну додатну цілу кількість миль з деякою цілочисельною швидкістю. Наприклад, спочатку вона може проїхати миль зі швидкістю миль на годину, а потім ще миль зі швидкістю миль на годину. Сумарна довжина всіх ділянок також дорівнює милям. Максимальна швидкість трактора фермера Джона становить миль на годину.
За наведеною вище інформацією визначте максимальне перевищення встановленого обмеження швидкості, якого Бессі припустилася на якійсь ділянці свого шляху.
У першому рядку містяться два цілих числа і . У наступних рядках описуються ділянки дороги: у кожному рядку вказано два цілих числа — довжина ділянки та встановлене на ній обмеження швидкості.
У наступних рядках описуються ділянки шляху Бессі: у кожному рядку вказано два цілих числа — довжина ділянки та швидкість, з якою Бессі рухалася нею.
Виведіть одне ціле число — максимальне перевищення встановленого обмеження швидкості, допущене Бессі на якійсь ділянці шляху. Якщо Бессі ніде не перевищувала швидкість, виведіть .
У цьому прикладі дорога складається з трьох ділянок: миль з обмеженням швидкості миль на годину, потім миль з обмеженням миль на годину і ще миль з обмеженням миль на годину.
Бессі проїжджає дорогу також трьома ділянками: миль зі швидкістю миль на годину, миль зі швидкістю миль на годину і миль зі швидкістю миль на годину.
На першій ділянці вона лише трохи перевищує швидкість, проте на останній ділянці порушення виявляється найсерйознішим: на деякій її частині вона перевищує встановлене обмеження на миль на годину. Тому правильна відповідь — .
Приклад 1