A. Bessie and Trap
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Farmer Nhoj has trapped Bessie in his dungeon! The dungeon consists of $$$N$$$ rooms numbered $$$1$$$ to $$$N$$$, and Bessie must visit them in order from room $$$1$$$ to room $$$N$$$.

To enter room $$$i$$$, Bessie must have at least $$$a_i$$$ keys. After entering room $$$i$$$, she immediately finds and picks up $$$b_i$$$ loose keys. Bessie can carry any number of keys, and keys are not consumed when opening a door.

Before she starts, Bessie may borrow some non-negative integer number of keys from a suspicious dungeon goblin named Kevin. What is the minimum number of keys Bessie needs to borrow in order to visit all $$$N$$$ rooms?

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 10^6$$$).

The next $$$N$$$ lines contain two space-separated integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^9$$$) — the number of keys needed to enter room $$$i$$$ and the number of keys found inside room $$$i$$$.

Output

Output a single non-negative integer: the minimum number of keys Bessie needs to borrow from Kevin.

Example
Input
4
2 1
5 3
3 2
9 0
Output
4
Note

It can be shown that Bessie must borrow at least $$$4$$$ keys.

  • Room $$$1$$$ ($$$a = 2$$$, $$$b = 1$$$): Bessie has $$$4$$$ keys, which meets the requirement. She picks up $$$1$$$ key, now having $$$5$$$.
  • Room $$$2$$$ ($$$a = 5$$$, $$$b = 3$$$): Bessie has $$$5$$$ keys, which meets the requirement. She picks up $$$3$$$ keys, now having $$$8$$$.
  • Room $$$3$$$ ($$$a = 3$$$, $$$b = 2$$$): Bessie has $$$8$$$ keys. She picks up $$$2$$$ keys, now having $$$10$$$.
  • Room $$$4$$$ ($$$a = 9$$$, $$$b = 0$$$): Bessie has $$$10$$$ keys. She picks up $$$0$$$ keys.