15615번 - The Prices 다국어

Byteasar works as a Purchasing Manager at one of Byteotian restaurants. Every evening he receives a shopping list from his manager. Food products must be purchased the next day, in the morning. Byteasar should buy exactly one piece of each product from the list. Manager is always pressing that the total costs are as little as possible.

Byteasar sits down in the evening with his computer and checks the prices of all needed products at local grocery wholesalers. He also knows the cost of the trips from the restaurant to each wholesale and back. Now Byteasar must decide which products are to be purchased at each of the warehouses.

For each wholesale, where Byteasar decided to buy some products, he does as follows. He would go from the restaurant to the warehouse, will do the shopping and immediately bring the purchased products back to the restaurant. Luckily, the boot of his car is big enough that it eliminates the need to visit any of the warehouses more than once, as all the purchased goods can be delivered in one go. Food products are highly perishable, so during one trip Byteasar can make purchases only at one warehouse.

Write a program that will help Byteasar to calculate the cheapest way of making all the purchases.

The first line of input contains two integers n and m (1 ≤ n ≤ 100, 1 ≤ m ≤ 16) denoting the number of wholesalers and the number of products that Byteasar should buy. Next n lines contain descriptions of the prices at individual wholesalers.

The first number in the i-th of these lines, d_i (1 ≤ d_i ≤ 1,000,000), describes the trip cost from the restaurant to the i-th warehouse (including the return cost). It is followed by a sequence of m integers c_i,1, c_i,2, ..., c_i,m (1 ≤ c_i,j ≤ 1,000,000): number c_i,j denotes the price of j-th product in the i-th warehouse.

Your program should output a single line containing a single integer denoting the sum of the product prices and the cost of the trips to warehouses selected by Byteasar in the cheapest possible purchase plan.

Byteasar buys the product number 2 in the first warehouse, and all the other products in the second one. So he does not have to visit the third warehouse.