Даны три мультимножества пар цветных палок:
- \(R\) пар красных палок, у первой пары длины равны \(r_1\), у второй пары длины равны \(r_2\), \(\dots\), у \(R\)-й пары длины равны \(r_R\);
- \(G\) пар зеленых палок, у первой пары длины равны \(g_1\), у второй пары длины равны \(g_2\), \(\dots\), у \(G\)-й пары длины равны \(g_G\);
- \(B\) пар синих палок, у первой пары длины равны \(b_1\), у второй пары длины равны \(b_2\), \(\dots\), у \(B\)-й пары длины равны \(b_B\).
Вы собираете прямоугольники из этих пар палок следующим образом:
- взять пару палок одного цвета;
- взять пару палок другого цвета, отличного от первого;
- прибавить площадь полученного прямоугольника к суммарной площади.
В итоге получатся такие прямоугольники, что противоположные стороны у них одного цвета, а соседние стороны различных цветов.
Каждая пара палок может быть использована не более одного раза, некоторые пары можно не использовать. Не разрешается разбивать пару палок на отдельные палки.
Какую максимальную суммарную площадь можно получить?
Выходные данные
Выведите максимально возможную суммарную площадь построенных прямоугольников.
Примечание
В первом примере можно построить один из следующих прямоугольников: красный и зеленый со сторонами \(3\) и \(5\), красный и синий со сторонами \(3\) и \(4\) и зеленый и синий со сторонами \(5\) и \(4\). Лучшая площадь из них равна \(4 \times 5 = 20\).
Во втором примере лучшие прямоугольники: красный/синий \(9 \times 8\), красный/синий \(5 \times 5\), зеленый/синий \(2 \times 1\). Суммарная площадь равна \(72 + 25 + 2 = 99\).
В третьем примере лучшие прямоугольники: красный/зеленый \(19 \times 8\) и красный/синий \(20 \times 11\). Суммарная площадь равна \(152 + 220 = 372\). Обратите внимание, что больше прямоугольников нельзя построить, потому что не разрешается иметь обе взятые пары одного цвета.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 1
3
5
4
|
20
|
|
2
|
2 1 3
9 5
1
2 8 5
|
99
|
|
3
|
10 1 1
11 7 20 15 19 14 2 4 13 14
8
11
|
372
|