
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 mtuple like (v_{1}, v_{2}, ... , v_{m}) (v_{i} 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 C_{i} and C_{j} 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 ~ Input 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 mtuples are positive and no more than 1000. There is a blank line between consecutive cases. Output For each test case, output the largest difference you can get when choosing 2 combos. Sample Input
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 Sample Output
8 28 Author: HE, Xing Source: ZOJ Monthly, December 2009 