Preparation for the Holiday#4063
Preparing for the holiday involves several considerations: deciding what to wear, whom to invite, and what menu to offer your guests, among others. One key task is grocery shopping — you want to offer a diverse spread while minimizing expenses.
Suppose you need to buy types of products to complete your menu. These groceries can be purchased from different stores. Thanks to the Internet, you know which stores have the products you need and at what prices.
There are "direct" paths of known lengths between all stores, as well as between your home and each store. A path is considered "direct" if traveling from one point to another doesn't require passing through a third known point, whether it's your home or another store. Assume that all paths allow two-way traffic.
Given the following information:
the number of products;
the quantities needed for each product;
the number of stores;
the availability and prices of products in the stores;
the lengths of "direct" paths between route points;
the cost of fuel per unit distance,
your task is to determine the minimum amount of money needed to purchase the groceries, factoring in both the cost of the products and the fuel expenses for traveling to the stores. The trip must start and end at your home.
The first line contains two integers and , separated by a space — the number of products and stores, respectively (1 \le P \le 5, 1 \le M \le 15).
The second line lists integers, separated by spaces — the quantities needed for each product (1 \le P_i \le 100, 1 \le i \le P).
The next lines each contain integers, separated by spaces — the prices of the products in each store (0 \le C_{ji} \le 100, 1 \le i \le P, 1 \le j \le M). A price of indicates the product is not available in that store. It is guaranteed that each product is available in at least one store, and that each store sells at least one product.
The following line contains integers, separated by spaces — the distances of the "direct" paths from your home to the -th store (1 \le L_j \le 100, 1 \le j \le M).
Each of the next M-1 lines (-th line) contains (M-k) integers, separated by spaces — the distances of the "direct" paths between the -th store and all stores numbered greater than (-th stores) (1 \le S_{kn} \le 100).
The final line contains one integer — the cost of fuel per unit distance (1 \le T \le 100).
The output should be a single integer — the minimum total cost of purchasing the groceries, including the fuel expenses.
Example (see figure): the bold path indicates the route, and the framed areas indicate the places of purchase.
Example 1