Перед сном Рита решила поиграть в игру на телефоне. Дан массив целых чисел, в котором каждый элемент обозначает длину стороны треугольника. Нужно определить максимально возможный периметр треугольника, составленного из сторон с длинами из заданного массива.
Помогите Рите скорее закончить игру и пойти спать.
Напомним, что из трёх отрезков с длинами a ≤ b ≤ c можно составить треугольник, если выполнено неравенство треугольника: c < a + b
Разберём пример:
даны длины сторон 6, 3, 3, 2. Попробуем в качестве наибольшей стороны выбрать 6. Неравенство треугольника не может выполниться, так как остались 3, 3, 2 —– максимальная сумма из них равна 6.
Без шестёрки оставшиеся три отрезка уже образуют треугольник со сторонами 3, 3, 2. Неравенство выполняется: 3 < 3 + 2. Периметр равен 3 + 3 + 2 = 8.
В первой строке записано количество отрезков n, 3≤ n≤ 10000.
Во второй строке записано n натуральных чисел, не превосходящих 10 000, –— длины отрезков.
Нужно вывести одно число —– наибольший периметр треугольника.
|
4 6 3 3 2 |
8
|
|
6 5 3 7 2 8 3 |
20
|