{"extraResources":{"example.01.mu":"TVXzATINCjEwIDIzOQ0K","example.02.mu":"TVXzATMNCjEgMiAyDQo="},"scoring":null,"notes":"","legend":"В одном чудесном краю, где солнце светит ярче, а цветы растут пышнее, жил-был добрый садовод Николай. С нетерпением он ждал, когда же наступит время открыть дачный сезон и заняться своим любимым делом: возделыванием грядок. \r\n\r\nОднажды, собравшись с силами, Николай привёз с собой волшебные пары досок. Доски в каждой паре были одинаковой длины, а доски из разных пар могли иметь разную длину. Николай мечтал создать \\textit{красивую} прямоугольную грядку, где бы росли самые прекрасные овощи и цветы. Для этого ему нужно было использовать все свои доски, не распиливая их, ставя парные доски на противоположные стороны прямоугольника.\r\n\r\nИ вот, стоя перед своим садом, Николай задумался: <<Какая площадь может получиться у красивой грядки?>> Помогите ему выяснить, какую минимальную и максимальную положительную площадь он может получить.\r\n","authorLogin":"Olympic_Bear","language":"russian","timeLimit":1000,"output":"Выведите два целых числа: минимальную и максимальную площадь красивой грядки.\r\n","inputFile":"stdin","outputFile":"stdout","input":"В первой строке записано целое число $n$~--- число пар досок ($2 \\le n \\le 7$).\r\n\r\nВо второй строке заданы $n$ целых чисел~--- длины досок в первой, второй, \\ldots, $n$-й паре.\r\nЭти числа лежат в пределах от $1$ до $10^8$.","authorName":"Nikolay Dubchuk","sampleTests":[{"output":"2390 2390\r\n","input":"2\r\n10 239\r\n","inputFile":"example.01","outputFile":"example.01.a"},{"output":"4 6\r\n","input":"3\r\n1 2 2\r\n","inputFile":"example.02","outputFile":"example.02.a"}],"name":"Грядка","interaction":null,"memoryLimit":1073741824,"tutorial":"Решение~--- для min площади минимальный размер доски умножить на сумму всех остальных, а для max~--- решить задачу о рюкзаке (набираем доски так, чтобы было ближе к квадрату). Решать можно полным перебором.\r\n\r\n\\textbf{Интересный факт} \r\n\r\nЕсли разрешить парные доски ставить, как угодно, а не напротив друг друга, то max площадь можно улучшить. \r\n\r\nПример: (1 11 101 111 200 20)\r\n\r\nМожно построить квадрат со стороной 222: \r\n200 + 20 + 1 * 2 = 111 * 2 = 101 * 2 + 20 = 11 * 2 + 200 \r\n\r\nЕсли парные доски надо ставить напротив друг друга, то доску 111 не добить до стороны 222, так как нет способа набрать 111 подмножеством чисел 1, 11, 101, 20, 200."}