Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Цветные прямоугольники
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны три мультимножества пар цветных палок:

  • $$$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$$$.

Вы собираете прямоугольники из этих пар палок следующим образом:

  1. взять пару палок одного цвета;
  2. взять пару палок другого цвета, отличного от первого;
  3. прибавить площадь полученного прямоугольника к суммарной площади.

В итоге получатся такие прямоугольники, что противоположные стороны у них одного цвета, а соседние стороны различных цветов.

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

Какую максимальную суммарную площадь можно получить?

Входные данные

В первой строке записаны три целых числа $$$R$$$, $$$G$$$, $$$B$$$ ($$$1 \le R, G, B \le 200$$$) — количество пар красных палок, количество пар зеленых палок и количество пар синих палок.

Во второй строке записаны $$$R$$$ целых чисел $$$r_1, r_2, \dots, r_R$$$ ($$$1 \le r_i \le 2000$$$) — длины палок в каждой паре красных палок.

В третьей строке записаны $$$G$$$ целых чисел $$$g_1, g_2, \dots, g_G$$$ ($$$1 \le g_i \le 2000$$$) — длины палок в каждой паре зеленых палок.

В четвертой строке записаны $$$B$$$ целых чисел $$$b_1, b_2, \dots, b_B$$$ ($$$1 \le b_i \le 2000$$$) — длины палок в каждой паре синих палок.

Выходные данные

Выведите максимально возможную суммарную площадь построенных прямоугольников.

Примеры
Входные данные
1 1 1
3
5
4
Выходные данные
20
Входные данные
2 1 3
9 5
1
2 8 5
Выходные данные
99
Входные данные
10 1 1
11 7 20 15 19 14 2 4 13 14
8
11
Выходные данные
372
Примечание

В первом примере можно построить один из следующих прямоугольников: красный и зеленый со сторонами $$$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$$$. Обратите внимание, что больше прямоугольников нельзя построить, потому что не разрешается иметь обе взятые пары одного цвета.