Preparation for the Holiday
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 P types of products to complete your menu. These groceries can be purchased from M 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.
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.
Input
The first line contains two integers P and M, separated by a space — the number of products and stores, respectively (1 ≤ P ≤ 5, 1 ≤ M ≤ 15).
The second line lists P integers, separated by spaces — the quantities needed for each product (1 ≤ Pi ≤ 100, 1 ≤ i ≤ P).
The next M lines each contain P integers, separated by spaces — the prices of the products in each store (0 ≤ Сji ≤ 100, 1 ≤ i ≤ P, 1 ≤ j ≤ M). A price of 0 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 M integers, separated by spaces — the distances of the "direct" paths from your home to the j-th store (1 ≤ Lj ≤ 100, 1 ≤ j ≤ M).
Each of the next M-1 lines (k-th line) contains (M-k) integers, separated by spaces — the distances of the "direct" paths between the k-th store and all stores numbered greater than k (n-th stores) (1 ≤ Skn ≤ 100).
The final line contains one integer T — the cost of fuel per unit distance (1 ≤ T ≤ 100).
Output
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.