A. Трамвай

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Шулууны хаант улс ганцхан трамвайн чиглэлтэй. Тэр чиглэл нь ганц замтай бөгөөд $1$-ээс $n$ хүртэл дугаарлагдсан $n$ ширхэг зогсоолтой. Трамвай уг зогсоолууд дээр $1$-ээс $n$ гэсэн дарааллаар зогсох ба $i$ дахь зогсоол дээр трамвайгаас яг $a_i$ зорчигч бууж яг $b_i$ зорчигч суудаг. Трамвай эхний зогсоол дээр ирэхдээ нэг ч зорчигчгүй ирэх ба сүүлчийн зогсоол дээр зогсохдоо мөн нэг ч зорчигчгүй болдог.

Таны даалгавар бол трамвайн явах, зогсох аль ч үед хүмүүс хангалттай багтаж байх хамгийн бага хүний багтаамжийг олох юм. Транвай зогсоолд зогсоход буух ёстой зорчигчид нь бүгд бууж байж суух зорчигчид нь транвайд ордоAг.

Оролт

Оролтын эхний мөрөнд зогсоолын тоо болох $n(2≤n≤1000)$ тоо байна.

Дараагийн $n$ мөр бүрт $a_i$, $b_i$ $(0≤ai,bi≤1000)$ гэсэн хос бүхэл тоонууд өгөгдөнө. Оролт нь дараах дүрэмд захирагдана.

  • $a_1=0$
  • $b_n=0$
  • Зогсоол бүр дээр буух зорчигчдийн тоо нь тухайн үед трамвайд байгаа зорчигчдийн тооноос хэтрэхгүй байна.
  • Сүүлчийн зогсоолд ирэхэд үлдсэн бүх зорчигч буудаг байхаар оролтууд өгөгдөх болно.

Гаралт

Трамвай хамгийн багадаа хэдэн хүний багтаамжтай байж болохыг илэрхийлэх ганц сөрөг биш бүхэл тоог хэвлэнэ.

[Орчуулга хяналт хийгдээгүй. ^_^ ... Codeforces Mongolian Translation Team]

Орчуулсан: Naranbayar

Жишээ тэстүүд

Оролт
4
0 3
2 5
4 2
4 0
Гаралт
6

Тэмдэглэл

For the first example, a capacity of 6 is sufficient:

  • At the first stop, the number of passengers inside the tram before arriving is 0. Then, 3 passengers enter the tram, and the number of passengers inside the tram becomes 3.
  • At the second stop, 2 passengers exit the tram (1 passenger remains inside). Then, 5 passengers enter the tram. There are 6 passengers inside the tram now.
  • At the third stop, 4 passengers exit the tram (2 passengers remain inside). Then, 2 passengers enter the tram. There are 4 passengers inside the tram now.
  • Finally, all the remaining passengers inside the tram exit the tram at the last stop. There are no passenger inside the tram now, which is in line with the constraints.

Since the number of passengers inside the tram never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible for the tram to have a capacity less than 6. Hence, 6 is the correct answer.

Сэтгэгдлүүдийг ачааллаж байна...