Cütlərə bölmə#10524
Фермер Джон обнаружил, что его коров легче доить, когда рядом с ними находится другая корова, оказывающая моральную поддержку. Поэтому он хочет взять своих коров (m \le 10^9, — чётное число) и разбить их на пар. Затем каждая пара коров будет отведена в отдельный стойло в коровнике для дойки. Дойка во всех стойлах будет происходить одновременно.
Чтобы немного усложнить задачу, каждая корова Фермера Джона даёт разное количество молока. Если в пару объединить коров с удоями и , то на их дойку вместе потребуется a + b единиц времени.
Помогите Фермеру Джону определить минимально возможное время, необходимое для дойки всех его коров, если разбить их на пары оптимальным образом.
В первой строке содержится n~(1 \le n \le 10^5). В каждой из следующих строк содержатся два целых числа и , означающие, что у Фермера Джона есть коров, каждая из которых даёт y~(1 \le y \le 10^9) единиц молока. Сумма всех равна , общему количеству коров. Гарантируется, что — чётное число.
Выведите минимальное время, необходимое для дойки всех коров Фермера Джона, если разбить их на пары оптимальным образом.
Предположим, например, что коровы с удоями и объединены в одну пару, а две коровы с удоем — в другую. Тогда дойка в каждом из двух стойл займёт единиц времени. Поскольку дойка во всех стойлах происходит одновременно, весь процесс завершится через единиц времени.
Любое другое разбиение на пары будет неоптимальным, поскольку в этом случае дойка хотя бы в одном стойле займёт более единиц времени.
Nümunə 1