Подготовка к празднику сопровождается различными хлопотами: что надеть, кого пригласить, какое меню предложить гостям и т.д. Одной из забот является закупка продуктов -- хочется разнообразить стол, при этом затратив как можно меньше финансовых средств. Будем считать, что для обеспечения выбранного меню нужно закупить \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{Пример (см. рисунок): }}жирным выделен путь движения, рамкой обведены места покупки.