Подготовка к празднику
Подготовка к празднику
Подготовка к празднику сопровождается различными хлопотами: что надеть, кого пригласить, какое меню предложить гостям и т.д. Одной из забот является закупка продуктов – хочется разнообразить стол, при этом затратив как можно меньше финансовых средств.
Будем считать, что для обеспечения выбранного меню нужно закупить P видов продуктов. Закупка продуктов возможна в M магазинах, при этом известно с помощью вездесущего Интернета, в каких магазинах и по какой цене имеются продукты в наличии.
Между всеми магазинами, а также между домом и каждым из магазинов есть "прямые" пути известной длины (путь считается "прямым", если при движении из одной точки в другую не происходит проезд через третью известную точку: дом или магазин). Будем считать, что все пути с двусторонним движением.
Требуется по известным:
количеству продуктов;
объемам закупки каждого из продуктов;
количеству магазинов;
наличию и цене продуктов в магазинах;
длинам "прямых" путей между точками маршрута;
стоимости затрат на топливо на единицу расстояния,
определить минимальную сумму денег, которые требуется затратить на покупку продуктов (затраты складываются из суммы денег, потраченных на продукты, и стоимости топлива, потраченного на поездку по магазинам). Поездка должна начинаться и заканчиваться дома.
Вхідні дані
Первая строка содержит два целых числа P и M, разделенных пробелом – количество продуктов и магазинов, соответственно (1 ≤ P ≤ 5, 1 ≤ M ≤ 15).
Вторая строка содержит P целых чисел, разделенных пробелами – объемы закупок каждого из продуктов (1 ≤ Pi ≤ 100, 1 ≤ i ≤ P).
Следующие M строк содержат по P целых чисел, разделенных пробелами – цены продуктов в магазинах (0 ≤ Сji ≤ 100, 1 ≤ i ≤ P, 1 ≤ j ≤ M). Значение цены 0 означает, что в магазине продукта нет. Гарантируется, что каждый продукт можно купить хотя бы в одном магазине. Гарантируется, что в каждом магазине продается хотя бы один продукт.
Следующая строка содержит M целых чисел, разделенных пробелами – расстояние "прямых" путей от дома до j-го магазина (1 ≤ Lj ≤ 100, 1 ≤ j ≤ M).
Каждая из следующих M-1 строк (k-ая строка) содержат по (M-k) целых чисел, разделенных пробелами – расстояния "прямого" пути между k-ым магазином и всеми магазинами, имеющими номер больше k (n-ми магазинами) (1 ≤ Skn ≤ 100).
Последняя строка содержит одно целое число T – стоимость затрат на топливо на единицу расстояния (1 ≤ T ≤ 100).
Вихідні дані
Выходной файл должен содержать одно целое число – минимальную сумму денег, которые требуется потратить на закупку продуктов с учетом стоимости затраченного топлива.
Пример (см. рисунок): жирным выделен путь движения, рамкой обведены места покупки.
Приклад
3 3 10 20 15 3 4 0 4 0 5 0 3 5 4 2 6 5 3 7 2
191