Input file name: input.txt

Output file name: output.txt

Time limit: from 1 s to 4 s

Memory limit: no

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

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

Input

В первой строке находятся целые числа n и m (1 ≤ n, m ≤ 300) — число вышек и заводов соответственно. Во второй строке через пробел перечислены n целых чисел — значения ai (1 ≤ ai ≤ 30000). В третьей строке через пробел перечислены m целых чисел — значения bj (1 ≤ bj ≤ 30000). Сумма всех ai равна сумме всех bj. В последующих n строках по m целых чисел записаны стоимости транспортировки; j-е число в (i + 3)-й строке задаёт значение cij (1 ≤ cij ≤ 109).

Output

В единственной строке выведите одно целое число — минимальную величину затрат на транспортировку при условии максимизации объёма переработки.