AVT VSU - Problem 1809. Sale of cucumbers

1809. Sale of cucumbers

Time Limit:	2 seconds
Memory Limit:	524288KB
Points:	100

На m дачных участках, находящихся в разных районах области, произрастает определенное количество единиц огурцов. Эту продукцию требуется доставить в n магазинов. В каждую из этих точек продажи необходимо доставить определенное количество огурцов. Стоимость перевозки единицы продукции с каждого дачного участка в каждый пункт продажи известна. Требуется так распределить поставки огурцов, чтобы общая стоимость перевозок была бы минимальной.

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

В первой строке даны 2 целых числа: 2 ≤ m ≤ 10 - количество огородов и 2 ≤ n ≤ 10 - количество магазинов, во второй строчке записаны m целых чисел 0 ≤ a_i ≤ 1000 - количества огурцов на каждом из огородов, в третьей строчке n целых чисел 0 ≤ b_j ≤ 1000 - количества огурцов, которые нужно доставить в каждый из магазинов, далее идёт таблица из m сток и n столбцов, на пересечении i-ой строки и j-ого столбца находится целое число 0 ≤ c_ij ≤ 1000 - стоимость перевозки (тариф) единицы продукции от i-го огорода в j-й магазин.

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

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

Пример

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

3 5
15 25 20
20 12 5 8 15
1 0 3 4 2
5 1 2 3 3
4 8 1 4 3

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

Примечание

С первого огорода в первый магазин везём 15 кг огурцов, со второго огорода во второй магазин - 12 кг огурцов, со второго огорода в четвёртый магазин - 8 кг огурцов, с третьего огорода в первый магазин - 5 кг огурцов, со второго в пятый - 5 кг, с третьего огорода в третий магазин - тоже 5 кг, и оставшиеся 10 кг везём с третьего огорода в пятый магазин. Общая стоимость перевозок 1·15 + 1·12 + 3·8 + 3·5 + 4·5 + 1·5 + 3·10 = 121

Remote Training on Programming

1809. Sale of cucumbers