M. Восхождение

Фермер отправил $n$ коров подняться на гору и вернуться обратно.

Корове $i$ нужно $u_i$ времени, чтобы подняться, и $d_i$ времени, чтобы спуститься. И подъём, и спуск требуют помощника, а помощников двое: один помогает только подниматься, другой — только спускаться. Поэтому в любой момент поднимается не более одной коровы и спускается не более одной.

Поднявшиеся коровы могут ждать на вершине сколько угодно, и спускаться они могут не в том порядке, в котором поднимались.

Найдите наименьшее время, за которое все коровы поднимутся и вернутся.

Первая строка содержит число $n$ ($1 \le n \le 2 \cdot 10^5$).

Следующие $n$ строк содержат по два числа $u_i$ и $d_i$ ($1 \le u_i, d_i \le 5 \cdot 10^4$).

Одно число — наименьшее суммарное время.