In dinosaur language, the chocolate eggs drawn above are called fetters. Dino loves to eat fetters. They are a real source of energy for him, he also collects a collection of toys that go out of them. Today for the next n days, Dino bought 2 * n fetters. He made it a habit to eat 1 in the morning and 1 in the evening. This allows him to maintain energy at a high level.

Dino bought magical fetters that can give different energies depending on whether they are eaten in the morning or evening. We know how much energy one fetter eaten in the morning and in the evening gives.

Dino is very smart and during these n days he plans to eat these fetters in such a way as to get the maximum energy from them at the end.

Find the maximum amount of energy that Dino can receive.

Input

First line contains number of days n (1 ≤ n ≤ 105). Each of the next 2 * n lines contains two integers si and ai (1 ≤ si, ai ≤ 109), meaning the energy of one fetter eaten in the morning and in the evening.

Output

Print the maximum amount of energy that Dino can receive.