Azərbaycan Respublika Olimpiadasının yarımfinalı 2019-2020
Dino and fetters
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.
First line contains number of days n (1 ≤ n ≤
105). Each of the next 2 * n lines contains two integers
ai (1 ≤
109), meaning the energy of one fetter eaten in the morning and in the evening.
Print the maximum amount of energy that Dino can receive.
1 5 6 4 3
2 3 6 7 1 4 9 10 11