## Inaho XI

View as PDF

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

Author:
Problem type

Given points in dimensional space, find the minimum "surface area" of a hyperrectangle required to contain all points modulo .

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

#### Input Specification

The first line will contain two space-separated integers,  , the number of dimensions and the number of points respectively.

The next lines will each contain integers,  .

#### Output Specification

Output the minimum "surface area" of a hyperrectangle required to contain all points, modulo .

##### Subtask 1 [10%]  ##### Subtask 2 [20%] #### 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