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