Задачи
Подготовка к празднику
Подготовка к празднику
Подготовка к празднику сопровождается различными хлопотами: что надеть, кого пригласить, какое меню предложить гостям и т.д. Одной из забот является закупка продуктов -- хочется разнообразить стол, при этом затратив как можно меньше финансовых средств.
Будем считать, что для обеспечения выбранного меню нужно закупить \textbf{P} видов продуктов. Закупка продуктов возможна в \textbf{M} магазинах, при этом известно с помощью вездесущего Интернета, в каких магазинах и по какой цене имеются продукты в наличии.
Между всеми магазинами, а также между домом и каждым из магазинов есть "прямые" пути известной длины (путь считается "прямым", если при движении из одной точки в другую не происходит проезд через третью известную точку: дом или магазин). Будем считать, что \textbf{все пути с двусторонним движением}.
Требуется по известным:
\begin{itemize}
\item количеству продуктов;
\item объемам закупки каждого из продуктов;
\item количеству магазинов;
\item наличию и цене продуктов в магазинах;
\item длинам "прямых" путей между точками маршрута;
\item стоимости затрат на топливо на единицу расстояния,
\end{itemize}
определить минимальную сумму денег, которые требуется затратить на покупку продуктов (затраты складываются из суммы денег, потраченных на продукты, и стоимости топлива, потраченного на поездку по магазинам). Поездка должна начинаться и заканчиваться дома.
\includegraphics{https://static.e-olymp.com/content/52/52fd615e71f12ac551fabc929cbd43590977993f.jpg}
\InputFile
Первая строка содержит два целых числа \textbf{P} и \textbf{M}, разделенных пробелом -- количество продуктов и магазинов, соответственно (\textbf{1} ≤ \textbf{P} ≤ \textbf{5}, \textbf{1} ≤ \textbf{M} ≤ \textbf{15}).
Вторая строка содержит \textbf{P} целых чисел, разделенных пробелами -- объемы закупок каждого из продуктов (\textbf{1} ≤\textbf{Pi} ≤ \textbf{100}, \textbf{1} ≤ \textbf{i} ≤ \textbf{P}).
Следующие \textbf{M} строк содержат по \textbf{P} целых чисел, разделенных пробелами -- цены продуктов в магазинах (\textbf{0} ≤ \textbf{Сji}≤ \textbf{100}, \textbf{1} ≤ \textbf{i} ≤ \textbf{P}, \textbf{1} ≤ \textbf{j} ≤ \textbf{M}). \textbf{Значение цены 0 означает, что в магазине продукта нет}. Гарантируется, что каждый продукт можно купить хотя бы в одном магазине. Гарантируется, что в каждом магазине продается хотя бы один продукт.
Следующая строка содержит \textbf{M} целых чисел, разделенных пробелами -- расстояние "прямых" путей от дома до \textbf{j}-го магазина (\textbf{1} ≤ \textbf{Lj} ≤ \textbf{100}, \textbf{1} ≤ \textbf{j} ≤ \textbf{M}).
Каждая из следующих \textbf{M-1} строк (\textbf{k}-ая строка) содержат по (\textbf{M}-\textbf{k}) целых чисел, разделенных пробелами -- расстояния "прямого" пути между \textbf{k}-ым магазином и всеми магазинами, имеющими номер больше \textbf{k} (\textbf{n}-ми магазинами) (\textbf{1} ≤ \textbf{Skn} ≤ \textbf{100}).
Последняя строка содержит одно целое число \textbf{T} -- стоимость затрат на топливо на единицу расстояния (\textbf{1} ≤ \textbf{T} ≤\textbf{100}).
\OutputFile
Выходной файл должен содержать одно целое число -- минимальную сумму денег, которые требуется потратить на закупку продуктов с учетом стоимости затраченного топлива.
\textit{\textbf{Пример (см. рисунок): }}жирным выделен путь движения, рамкой обведены места покупки.
Входные данные #1
3 3 10 20 15 3 4 0 4 0 5 0 3 5 4 2 6 5 3 7 2
Выходные данные #1
191