Planet W is a planet with a pleasant climate and a high concentration of species, much like Earth. After years of research, xenobiologists have discovered tens of thousands of species, and this number continues to grow.

The creatures on Planet W are fascinating. Some species are very friendly, spending their days together and staying inseparable; however, others are hostile, and fights are inevitable whenever they meet. To better understand the degree of friendliness between them, xenobiologists hope to perform some quantitative calculations. They have discovered that the friendliness between two species depends on their $K$ attributes, which we can label as attribute 1, attribute 2, ..., attribute $K$. These attributes can be quantified. Xenobiologists have found that the greater the difference in the first $K-1$ attributes, the friendlier the two species are; however, attribute $K$ is different: the smaller the difference in this attribute, the friendlier the two species are.

Therefore, they hypothesize that the friendliness between two species can be quantified by the following formula:

$$Friendliness = \left( \sum_{i=1}^{K-1} C_i \times \text{difference of attribute } i \right) - C_K \times \text{difference of attribute } K$$

where $C_i$ are non-negative constants.

If the various attributes of each species are known, it is easy to calculate the friendliness between them using the above formula. Now, the xenobiologists want to ask: among the species discovered so far, which pair is the friendliest? What is the degree of friendliness between them?

Input

The first line of the input contains two integers $N$ and $K$, representing the number of species discovered so far and the number of attributes, respectively.

The second line contains $K$ non-negative integers $C_i$, which are the constants required for calculating the friendliness.

The next $N$ lines describe each species, numbered 1, 2, ..., $N$ in order. Each line contains $K$ integers, providing the values for each attribute of that species, labeled as attribute 1, attribute 2, ..., attribute $K$ in order.

Output

The output contains two lines. The first line contains two integers $i$ and $j$ ($i \neq j$), representing the friendliest pair of species you found. If there is more than one friendliest pair, output any one of them.

The second line contains an integer representing the friendliness between species $i$ and species $j$.

Constraints

• $2 \le N \le 100,000$
• $2 \le K \le 5$
• $0 \le C_i \le 100$
• The value of each attribute for every species is between $-10000$ and $10000$ inclusive.
• The maximum friendliness is guaranteed to be greater than 0.

Examples

Input 1

5 3
1 2 3
-5 3 2
-2 3 0
0 5 9
3 4 -1
-10 -11 7

Output 1

3 5
36

Note 1

The friendliness between species 3 and 5 is $1 \times |0 - (-10)| + 2 \times |5 - (-11)| - 3 \times |9 - 7| = 36$.