OI题库

【题目描述】

W星球是一个和地球一样气候适宜、物种聚集的星球。经过多年的研究，外星生物学家们已经发现了数万种生物，而且这个数字还在不断增大。

W星球上的生物很有趣，有些生物之间很友好，朝夕相伴，形影不离；但有些却很敌对，一见面就难免发生战斗。为了能够更好地了解它们之间的友好程度，外星生物学家希望进行一些量化的计算。他们发现，两种生物之间的友好程度和它们的K种属性有关，暂且将它们编号为属性1、属性2、……、属性K，这些属性都是可以进行量化的。外星生物学家研究发现，如果前K-1种属性的差别越大，这两种生物就越友好；但是属性K与众不同，这种属性差别越小的两种生物越友好。

因此他们猜想是不是可以用这样一个公式量化两种生物之间的友好程度：

，其中Ci是非负常数。如果知道了每种生物的各种属性，利用上述公式就很容易算出它们之间的友好程度了。现在，外星生物学家们想问一问：在目前发现的这些生物当中，关系最友好的那对生物是哪一对呢？它们之间的友好程度是多少？

【输入格式】

输入文件的第一行是两个整数N和K，分别表示目前发现的生物种数和属性的种数。

第二行有K个非负整数Ci，即计算友好程度时所需的常数。

接下来的N行，描述每种生物，按照先后顺序依次编号为生物1、生物2、……、生物N。每一行都有K个整数，给出该种生物的各项属性值，按照先后顺序依次编号为属性1、属性2、……、属性K。

【输出格式】

输出一行一个整数，即最大的友好程度。

【样例输入】

5 3

1 2 3

-5 3 2

-2 3 0

0 5 9

3 4 -1

-10 -11 7

【样例输出】

36

【提示】

样例解释：生物3和5之间的友好程度为1*|0-(-10)|+2*|5-(-11)|-3*|9-7|=36。

数据范围：

2 ≤ N ≤ 100,000

2 ≤ K ≤ 5

0 ≤ Ci ≤ 100。

每种生物的各项属性值不小于-10000且不大于10000

最大的友好程度一定大于0

【来源】

NOI 2005冬令营