P4131 [WC2005] Friendly Creatures

Planet $W$ is a world with an Earth-like climate and a diverse collection of species. After years of research, xenobiologists have discovered tens of thousands of species, and the number keeps growing. Species on planet $W$ are interesting: some pairs are very friendly, always together and inseparable; others are hostile and fight upon meeting. To better understand their degrees of friendliness, the xenobiologists want to run some quantitative calculations. They have found that the friendliness between two species depends on their $K$ attributes, temporarily numbered as attribute $1$, attribute $2$, …, attribute $K$, all of which are quantifiable. Their research suggests that the larger the differences in the first $K-1$ attributes, the friendlier the pair; but attribute $K$ is special: the smaller the difference in this attribute, the friendlier the pair. Therefore, they conjecture that the following formula can quantify the friendliness between two species: $Friendliness=(\sum_{i=1}^{k-1} C_id_i)-C_Kd_K$, where $C_i$ are non-negative constants and $d_i$ is the difference in attribute $i$ (i.e., the absolute difference). If the attributes of each species are known, the above formula makes it easy to compute the friendliness between any pair. Now the xenobiologists ask: among the species discovered so far, which pair is the friendliest, and what is their friendliness?

The first line contains two integers $N$ and $K$, the number of discovered species and the number of attributes, respectively. The second line contains $K$ non-negative integers $C_i$, the constants used to compute the friendliness. The next $N$ lines describe each species, numbered in order as species $1$, species $2$, …, species $N$. Each line contains $K$ integers, giving the values of attributes $1$, $2$, …, $K$ for that species.

Output two lines. The first line contains two integers $i$ and $j$ ($i \neq j$), indicating that the friendliest pair you found is species $i$ and species $j$. If there is more than one friendliest pair, output any one of them. The second line contains an integer, the friendliness between species $i$ and species $j$.

[Sample Explanation] The friendliness between species $3$ and $5$ is $1\times |0-(-10)|+2\times |5-(-11)|-3\times |9-7|=36$. [Constraints] - $2 \leq N \leq 100{,}000$. - $2 \leq K \leq 5$. - $0 \leq C_i \leq 100$. - Each attribute value is at least $-10000$ and at most $10000$. - The maximum friendliness is guaranteed to be greater than $0$. Translated by ChatGPT 5