W Planet Organisms’ Friendliness

On planet \(W\), a world with a climate similar to Earth, scientists have discovered tens of thousands of organisms. Each organism is described by \(K\) quantitative attributes. The friendliness between two organisms is measured using a special formula. For the first \(K-1\) attributes, a larger difference indicates a higher friendliness, while for the \(K\)th attribute, a smaller difference indicates a higher friendliness. The formula to calculate the friendliness between two organisms is:

[ Friendliness = \left(\sum_{i=1}^{K-1} C_i \cdot d_i\right) - C_K \cdot d_K, ]

where \(C_i\) are non-negative constants and \(d_i = |a_i - b_i|\) is the absolute difference of the \(i\)th attribute between the two organisms. Given the data of all discovered organisms, your task is to determine the pair of organisms with the maximum friendliness and output this pair (using 1-indexing) along with their friendliness score.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers \(n\) and \(K\), representing the number of organisms (with \(n \ge 2\)) and the number of attributes.
2. The second line contains \(K\) non-negative integers: \(C_1, C_2, \dots, C_K\), representing the weight constants for the attributes.
3. Each of the next \(n\) lines contains \(K\) integers, representing the quantitative attributes of one organism.

You may assume all values are within the appropriate range for 32-bit integers.

outputFormat

Output three space‐separated integers: the indices (1-indexed) of the two organisms that form the pair with the maximum friendliness, followed by their friendliness score. If there are multiple pairs with the same maximum friendliness, output the first pair encountered (with the smallest first index and then the smallest second index).

sample

3 3
2 3 4
1 2 3
4 0 5
2 2 1

1 2 4