Cakes

Once upon a time, in the very poor kingdom of Ragland, there lived a king and a queen (of beggars). They had only one daughter, the charming Pauperella, who was to marry the beautiful and astonishingly rich prince Goldteeth. Although the young princess protested, her parents insisted that the wedding take place in their own castle. They asked their excellent cook to prepare the wedding cakes — the famous wedding cakes of Ragland. But because they are not as well-off as one might expect of a royal couple, they have only this one cook and only one small oven, in which all the cakes must be baked.

The cook has to prepare $N$ different cakes. Preparing a cake consists of two phases. In the first phase the cook makes the dough and puts it into a form; in the second phase the cake is baked in the oven. Preparing the dough for the $i$-th cake takes $a_i$ seconds, and once the dough is ready the cake must be baked for $b_i$ seconds. (A cake need not be baked immediately after its dough is ready; the dough may sit in its form for a while.) The cook can prepare only one dough at a time, and at most one cake may be baking in the oven at any moment. The cakes may be prepared and baked in any order.

Find the minimum time needed to make all the cakes. You may assume that handling the oven (inserting a cake and removing a baked one) takes zero time.

The first line contains a positive integer $N$ ($N \le 1{,}000{,}000$) — the number of cakes to be made. Each of the next $N$ lines contains two positive integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 2{,}000{,}000{,}000$), where $a_i$ is the time needed to prepare the dough of the $i$-th cake and $b_i$ is the time needed to bake it.

Print a single line with the minimum time in which all the cakes can be made. You may assume that the answer does not exceed $2{,}000{,}000{,}000$.