ZOJ Problem Set - 3280
Mr Dill and his wife Mrs Dill enjoy delicacy very much. Now they are in the most luxurious restaurant in their city. When ordering dishes, a strange idea comes to them that they want to choose two combos with the largest difference. After arguing for a long time, they turn to the waiter. But the waiter is not good at mathematics, this may be a quite difficult problem for him.
The restaurant offers n combos. Each combo contains and only contains m nutrients. Then we can consider that each combo is a m-tuple like (v1, v2, ... , vm) (vi illustrates the amount of the ith nutrient). Besides, considering the different roles the m nutrients play, we specify m weights for each. Hence, the difference between two specified combos Ci and Cj defined as following:
Can you help the poor waiter to choose such two most different combos? You just need to tell me the largest difference ~
There are no more than 15 cases. Process to the end of file.
For each case, the first line contains two integers n (2 <= n <= 50000) and m (1 <= m <= 8). Then n lines follow and each line contains m integers to specify the n combos. The next line contains m integers means the weights for the nutrients. It is guaranteed that there exist at least two different combos. All weights are positive numbers and no more than 100. All elements in the n m-tuples are positive and no more than 1000.
There is a blank line between consecutive cases.
For each test case, output the largest difference you can get when choosing 2 combos.
2 2 1 3 4 8 1 1 4 4 1 1 1 2 1 1 2 3 1 2 3 4 2 3 4 5 5 4 3 2
Author: HE, Xing
Source: ZOJ Monthly, December 2009