Alice and Bob's Manhattan Collection Game

Alice and Bob are two beings living in a k-dimensional space. In this space there are 2n distinct feature points. The i-th feature point has coordinates \( (x_{i,1}, x_{i,2}, \ldots, x_{i,k}) \). The distance between any two points is defined by the Manhattan distance:

[ \text{dist}(i,j)=\sum_{p=1}^{k}|x_{i,p}-x_{j,p}|. ]

The two players take turns selecting one of the feature points – once a point is chosen it cannot be picked again. Alice picks first and puts her chosen points into set \(S_1\) while Bob puts his chosen points into set \(S_2\). The "value" of a set \(S\) is defined as the sum of the Manhattan distances between every pair of points contained in \(S\):

[ \text{val}(S)=\sum_{i,j \in S,; i<j} \text{dist}(i,j). ]

Alice wants to maximize \( \text{val}(S_1)-\text{val}(S_2) \) and Bob wants to minimize it. Assuming both players play optimally, compute the final value of \( \text{val}(S_1)-\text{val}(S_2) \).

inputFormat

The first line contains two integers n and k, where 2n is the number of points and k is the dimension of the space.

Then 2n lines follow, each containing k space‐separated integers representing the coordinates of each point.

outputFormat

Output a single integer: the final value of \( \text{val}(S_1)-\text{val}(S_2) \) when both players play optimally.

sample

1 2
0 0
1 1

0