Задача  53. «Нефтепереработка»

Время на тест 1 секунда


Условие

В некоторой стране имеются N нефтяных вышек, i-я из которых способна выкачать до ai тысяч баррелей нефти в сутки, и M нефтеперерабатывающих заводов, каждый из которых, в свою очередь, способен переработать до bj тысяч баррелей нефти в сутки. Заводы и вышки связаны трубопроводами; ввиду различных причин стоимость транспортировки одной тысячи баррелей от i-й вышки к j-му заводу составляет сij денежных единиц; объем перекачки неогриничен.

Учитывая, что вышки и заводы должны находится в производственном балансе, т.е. вся выкачиваемая нефть должна быть вовремя переработана (излишки нигде не должны сливаться или накапливаться), какое максимальное количество нефти в сутки может перерабатывать данная инфраструктура? На данный вопрос ответить относительно легко, поэтому нас интересует лишь величина минимальных возможных затрат среди всех максимальных по объему перерабатываемой нефти решений.

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

В первой строке входного файла input.txt находятся целые N и M (1 ≤ N, M ≤ 300) — число вышек и заводов соответственно. Во второй строке через пробел перечислены N целых чисел — значения ai (1 ≤ ai ≤ 30000). В третьей строке через пробел перечислены M целых чисел — значения bj (1 ≤ bj ≤ 30000). Сумма всех ai равна сумме всех bj. В последующих N строках по M целых чисел записаны стоимости транспортировки; j-е число в (i+2)-й строке задает значение сij (1 ≤ cij ≤ 10000).

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

В единственной строке выходного файла output.txt выведите одно целое число — минимальную величину затрат на транспортировку при условии максимизации объема переработки. Гарантируется, что ответ можно поместить в знаковое тридцатидвухбитное целое.

Пример входных данных

3 4
3 6 7
2 5 1 8
1 2 3 4
8 7 6 5
9 12 10 11

Пример выходных данных

110