Задача D. Башня из блоков

Автор:Д. Попов, М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

Вася выбрал три взаимно перпендикулярные грани блока и разрезал блок:

  1. N − 1 раз параллельно первой грани, получив слои толщиной a1, …, aN,
  2. M − 1 раз параллельно второй грани, получив слои толщиной b1, …, bM,
  3. K − 1 раз параллельно третьей грани, получив слои толщиной c1, …, cK.

После всех разрезов блок разделился на N × M × K блоков-параллелепипедов.

В завершение представления Вася хочет выстроить эти блоки вертикально, сложив их друг на друга в башню одной гранью на другую. При этом любой блок благодаря способностям Васи может лечь любой гранью на любую грань любого другого блока.

Чтобы произвести максимальное впечатление, Вася хочет, чтобы башня получилась максимально высокой.

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

Формат входного файла

Первая строка входного файла содержит три целых числа N M K

Вторая строка содержит N целых чисел ai — толщина слоёв, параллельных первой грани.

Третья строка содержит M целых чисел bi — толщина слоёв, параллельных второй грани.

Четвертая строка содержит K целых чисел ci — толщина слоёв, параллельных третей грани.

Формат выходного файла

Выходной файл должен содержать единственное целое число — максимальную высоту башни.

Ограничения

1 ≤ N, M, K ≤ 105

1 ≤ ai, bi, ci ≤ 103

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 1
2
3
4
4
2
2 1 2
1 10
10
8 2
40

0.044s 0.007s 17