Hey buddy,

How are you? Last night I saw you programming on Hackerrank in my burger restauraunt. So I wonder if you can help me out on a problem I've been struggling with for like 10 hours.

It is called "The Challenge" and for some reasons the online judge always gives me TLE (Time Limit Exceeded). My code and the important part of the problem are attached with this email. I omitted the problem statement because it was three A4 sheets long and included a very boring story.

I want you to send me an AC (Accepted) code so that I can learn from you and figure out why my implementation is so slow.

Your favourite burger cook,

Jim

PS: Tuesday is "Happy Burgers Day" so there is a -% discount on all burgers!

the_challenge.psc

### author: jim
### problem: the challenge
### status: TLE
### a..b : iterate from a to b ( both inclusive )
define n, d as integers
define H as an integer array
define X as a two-dimensional integer array

function m(i, j)
   for k = 1..d
      dist = dist + abs(X[i][k] - X[j][k])

function main()
  read n and d from input
  for i = 1..n
     read H[i]
    for j = 1..d
      read X[i][j]  
  sum = 0
  for i = 1..n
      for j = i+1..n
       sum = sum + H[i] * H[j] * m(i, j)
  print sum mod 1000000009

the_challenge.pdf

Input Format

On the first line, you will be given and , then lines follow, describing the points. Each point is described as . So the first integer of each line is , then integers follow which will describe the values of point .

Output Format

Print the answer to the challenge modulo on a single line.

Constraints

Sample Input

3 3
5 1 2 3
7 2 3 4
8 4 5 6

Sample Output

801

Explanation

Compare point 1 and point 2: Our first term of the sum is .

Compare point 1 and point 3: The second term is

Compare point 2 and point 3: The final term will be

So the answer is .