Підготовка до свята#4063
Підготовка до свята завжди супроводжується безліччю турбот: що вдягнути, кого запросити, яке меню запропонувати гостям тощо. Одним із завдань є закупівля продуктів — хочеться урізноманітнити стіл, витративши при цьому якомога менше коштів.
Припустимо, що для реалізації обраного меню потрібно придбати видів продуктів. Закупівля можлива в магазинах, і завдяки всюдисущому Інтернету відомо, в яких магазинах і за якою ціною є продукти.
Між усіма магазинами, а також між домом і кожним із магазинів, існують "прямі" шляхи відомої довжини (шлях вважається "прямим", якщо при русі з однієї точки в іншу не відбувається проїзд через третю відому точку: дім або магазин). Всі шляхи є двосторонніми.
Необхідно, маючи такі дані:
кількість продуктів;
обсяги закупівлі кожного з продуктів;
кількість магазинів;
наявність і ціна продуктів у магазинах;
довжини "прямих" шляхів між точками маршруту;
вартість витрат на паливо на одиницю відстані,
визначити мінімальну суму грошей, яку потрібно витратити на покупку продуктів (витрати складаються із суми грошей, витрачених на продукти, і вартості пального, витраченого на поїздку по магазинах). Поїздка повинна починатися і закінчуватися вдома.
Перший рядок містить два цілі числа і , розділених пробілом — кількість продуктів і магазинів відповідно (1 \le P \le 5, 1 \le M \le 15).
Другий рядок містить цілих чисел, розділених пробілами — обсяги закупівель кожного з продуктів (1 \le P_i \le 100, 1 \le i \le P).
Наступні рядків містять по цілих чисел, розділених пробілами — ціни продуктів у магазинах (0 \le C_{ji} \le 100, 1 \le i \le P, 1 \le j \le M). Значення ціни означає, що в магазині продукту немає. Гарантується, що кожен продукт можна купити хоча б в одному магазині. Гарантується, що в кожному магазині продається хоча б один продукт.
Наступний рядок містить цілих чисел, розділених пробілами — відстань "прямих" шляхів від дому до -го магазину (1 \le L_j \le 100, 1 \le j \le M).
Кожен з наступних M-1 рядків (-ий рядок) містить по (M-k) цілих чисел, розділених пробілами — відстані "прямого" шляху між -им магазином і всіма магазинами, що мають номер більше (-ми магазинами) (1 \le S_{kn} \le 100).
Останній рядок містить одне ціле число — вартість витрат на паливо на одиницю відстані (1 \le T \le 100).
Вихідний файл повинен містити одне ціле число — мінімальну суму грошей, яку потрібно витратити на закупівлю продуктів з урахуванням вартості витраченого пального.
Приклад (див. рисунок): жирним виділено шлях руху, рамкою обведено місця покупки.
Приклад 1