## Inaho XI

View as PDF

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Given $$M$$ points in $$N$$ dimensional space, find the minimum "surface area" of a hyperrectangle required to contain all $$M$$ points modulo $$10^9+7$$.

As an example, the "surface area" of a $$2$$-dimensional hyperrectangle (rectangle) is the sum of its $$4$$ side lengths. The "surface area" of a $$3$$-dimensional hyperrectangle (rectangular prism) is the sum of the areas of the $$6$$ sides of the hyperrectangle.

#### Input Specification

The first line will contain two space-separated integers, $$N, M\ (2 \le N \le 10, 1 \le M \le 10^5)$$, the number of dimensions and the number of points respectively.

The next $$M$$ lines will each contain $$N$$ integers, $$a_{i_1}, a_{i_2}, \ldots, a_{i_N}\ (-10^9 \le a_{i_j} \le 10^9)$$.

#### Output Specification

Output the minimum "surface area" of a hyperrectangle required to contain all $$M$$ points, modulo $$10^9+7$$.

$$N = 2, M \le 100$$

$$M \le 100$$

No further constraints.

#### Sample Input 1

2 4
1 1
3 3
-1 2
0 0

#### Sample Output 1

14

#### Sample Input 2

5 3
1 4 2 3 4
0 -129 6 9 0
0 0 -10 9 5

#### Sample Output 2

183436