Codeforces Beta Round 87 (Div. 2 Only) |
---|
Закончено |
В Линейном Королевстве всего один трамвайный маршрут. На нем n остановок, пронумерованных от 1 до n в порядке следования трамвая. На i-ой остановке ai человек выходит из трамвая, а bi человек заходит в трамвай. Трамвай прибывает на первую остановку пустым. Также, когда трамвай прибывает на последнюю остановку, все пассажиры выходят, и трамвай уезжает пустым.
Ваша задача — найти минимальную возможную вместимость трамвая, такую, что количество пассажиров в трамвае в любой момент времени не превосходит эту вместимость. Учтите, что на каждой остановке все пассажиры выходят до того как какой-либо пассажир заходит.
В первой строке записано целое число n (2 ≤ n ≤ 1000) — количество остановок трамвая.
Далее следует n строк, в каждой — по два целых числа ai и bi (0 ≤ ai, bi ≤ 1000) — количество пассажиров, которые выходят из трамвая на i-ой остановке, и количество пассажиров, которые заходят в трамвай на i-ой остановке. Остановки перечислены в том же порядке, в котором их проезжает трамвай.
Выведите одно целое число — минимальную возможную вместимость трамвая. Допускается, что вместимость может быть равна нулю.
4
0 3
2 5
4 2
4 0
6
В первом примере достаточная вместимость — 6:
Так как количество пассажиров в трамвае в любой момент времени не превосходит 6, вместимость 6 — достаточна. Более того, вместимость не может быть меньше 6. Значит, 6 — правильный ответ.
Название |
---|