MEDSUM - Sum of Median

You are given n increasing sequences A1, A2, A3, ... , An. Each sequence have L values of integers.
Merge Ai and Aj obtained Aij have 2L values and Aij is increasing sequence. Median values of Aij is L-th value of Aij.

Example:
L = 5.
Ai = (1 3 4 5 6); Aj = (0 1 5 6 7).
Aij = (0 1 1 3 4 5 5 6 6 7).
Median value of Aij is 4.

Input

- The first line of input contains n, L (2 <= n <= 200; 1 <= L <= 20000).
- In the next n lines, the i-th line contains L integers of
<= 109 Ai.

Output

- Sum of all median value in module 109.

Example

Input:

3 6

1 2 3 4 5 6

3 4 5 6 7 8

0 0 1 1 2 2 Output: 8

Added by:Em là siêu nhân
Date:2013-01-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-12-20 14:33:16
I am unable to comprehend the sample case , can anyone explain why the output is 8 ? Thanks in advance .
2013-01-27 16:59:51 :D
I moved it to partial, because that how scoring is set. You can put it back in classical, if you change it to binary scoring.
2013-01-27 16:02:44 unidentified
@problem setter:what is the scoring criteria ??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.