eolymp
bolt
Try our new interface for solving problems
Problems

Подготовка к празднику

Подготовка к празднику

Time limit 0.5 seconds
Memory limit 16 MiB

Подготовка к празднику сопровождается различными хлопотами: что надеть, кого пригласить, какое меню предложить гостям и т.д. Одной из забот является закупка продуктов – хочется разнообразить стол, при этом затратив как можно меньше финансовых средств.

Будем считать, что для обеспечения выбранного меню нужно закупить P видов продуктов. Закупка продуктов возможна в M магазинах, при этом известно с помощью вездесущего Интернета, в каких магазинах и по какой цене имеются продукты в наличии.

Между всеми магазинами, а также между домом и каждым из магазинов есть "прямые" пути известной длины (путь считается "прямым", если при движении из одной точки в другую не происходит проезд через третью известную точку: дом или магазин). Будем считать, что все пути с двусторонним движением.

Требуется по известным:

  • количеству продуктов;

  • объемам закупки каждого из продуктов;

  • количеству магазинов;

  • наличию и цене продуктов в магазинах;

  • длинам "прямых" путей между точками маршрута;

  • стоимости затрат на топливо на единицу расстояния,

определить минимальную сумму денег, которые требуется затратить на покупку продуктов (затраты складываются из суммы денег, потраченных на продукты, и стоимости топлива, потраченного на поездку по магазинам). Поездка должна начинаться и заканчиваться дома.

Input data

Первая строка содержит два целых числа P и M, разделенных пробелом – количество продуктов и магазинов, соответственно (1P5, 1M15).

Вторая строка содержит P целых чисел, разделенных пробелами – объемы закупок каждого из продуктов (1Pi100, 1iP).

Следующие M строк содержат по P целых чисел, разделенных пробелами – цены продуктов в магазинах (0Сji100, 1iP, 1jM). Значение цены 0 означает, что в магазине продукта нет. Гарантируется, что каждый продукт можно купить хотя бы в одном магазине. Гарантируется, что в каждом магазине продается хотя бы один продукт.

Следующая строка содержит M целых чисел, разделенных пробелами – расстояние "прямых" путей от дома до j-го магазина (1Lj100, 1jM).

Каждая из следующих M-1 строк (k-ая строка) содержат по (M-k) целых чисел, разделенных пробелами – расстояния "прямого" пути между k-ым магазином и всеми магазинами, имеющими номер больше k (n-ми магазинами) (1Skn100).

Последняя строка содержит одно целое число T – стоимость затрат на топливо на единицу расстояния (1T100).

Output data

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

Пример (см. рисунок): жирным выделен путь движения, рамкой обведены места покупки.

Examples

Input example #1
3 3
10 20 15
3 4 0
4 0 5
0 3 5
4 2 6
5 3
7
2
Output example #1
191
Source Региональная олимпиада по программированию, СибГИУ, 2011