← run

cf-2065-d

1.000
2/2 tests· algorithms

Proposed solution

I'll solve this step by step.

## Problem Understanding

1. We have `n` arrays, each with `m` elements
2. We need to concatenate them in some order to form one array of `n*m` elements
3. The score is calculated as: sum of all prefix sums
4. We want to maximize this score

Let me trace through the first example:
- Arrays: [4,4] and [6,1]
- If we put [4,4] first: [4,4,6,1]
  - Prefix sums: 4, 8, 14, 15
  - Score: 4 + 8 + 14 + 15 = 41
- If we put [6,1] first: [6,1,4,4]
  - Prefix sums: 6, 7, 11, 15
  - Score: 6 + 7 + 11 + 15 = 39

So putting [4,4] first gives better score.

## Key Insight

Let's think about how to arrange the arrays optimally:
- For array `i` with elements `[a[i][1], a[i][2], ..., a[i][m]]`
- The contribution to total score depends on when this array is placed
- If array `i` is at position `j` (1-indexed), it contributes:
  - `a[i][1]` appears `n-j+1` times in prefix sums
  - `a[i][2]` appears `n-j+1` times in prefix sums  
  - ...
  - `a[i][m]` appears `n-j+1` times in prefix sums

Wait, let me reconsider this more carefully.

If array `i` is at position `j`, then:
- Element `a[i][1]` contributes to prefix sums of positions 1 through m in the final array
- Element `a[i][2]` contributes to prefix sums of positions 2 through m in the final array
- And so on...

Actually, let me think differently. 

If we have arrays A and B, and we want to decide whether A should come before B:
- If A comes first: score = (sum of A) + (sum of A + sum of B)
- If B comes first: score = (sum of B) + (sum of B + sum of A)

Wait, that's not right either. Let me re-read the definition.

The score is: `S_1 + S_2 + ... + S_k` where `S_i` is sum of first i elements.

Let's say we have two arrays [a,b] and [c,d].
If [a,b] comes first:
- Final array: [a,b,c,d]
- Prefix sums: a, a+b, a+b+c, a+b+c+d
- Score: a + (a+b) + (a+b+c) + (a+b+c+d) = 4a + 3b + 2c + 1d

If [c,d] comes first:
- Final array: [c,d,a,b]
- Prefix sums: c, c+d, c+d+a, c+d+a+b
- Score: c + (c+d) + (c+d+a) + (c+d+a+b) = 4c + 3d + 2a + 1b

So we want to maximize: 4a + 3b + 2c + 1d vs 4c + 3d + 2a + 1b
This is equivalent to comparing (4a + 3b + 2c + 1d) vs (4c + 3d + 2a + 1b)
Which is: 4a + 3b + 2c + 1d - 4c - 3d - 2a - 1b = 2a + 2b - 2c - 2d = 2(a+b-c-d)

So we should put array with larger (sum of elements) first.

Wait, that's not right either. Let me be more systematic.

Let's say we have two arrays `A` and `B`, each with `m` elements.
If A comes before B:
- Final array: [A[1], A[2], ..., A[m], B[1], B[2], ..., B[m]]
- Prefix sums: A[1], A[1]+A[2], ..., A[1]+...+A[m], A[1]+...+A[m]+B[1], ..., A[1]+...+A[m]+B[1]+...+B[m]
- Score = (m*A[1] + (m-1)*A[2] + ... + 1*A[m]) + (m*B[1] + (m-1)*B[2] + ... + 1*B[m])

If B comes before A:
- Final array: [B[1], B[2], ..., B[m], A[1], A[2], ..., A[m]]
- Prefix sums: B[1], B[1]+B[2], ..., B[1]+...+B[m], B[1]+...+B[m]+A[1], ..., B[1]+...+B[m]+A[1]+...+A[m]
- Score = (m*B[1] + (m-1)*B[2] + ... + 1*B[m]) + (m*A[1] + (m-1)*A[2] + ... + 1*A[m])

The difference is: 
(m*A[1] + (m-1)*A[2] + ... + 1*A[m]) + (m*B[1] + (m-1)*B[2] + ... + 1*B[m]) - (m*B[1] + (m-1)*B[2] + ... + 1*B[m]) - (m*A[1] + (m-1)*A[2] + ... + 1*A[m])
= 0

This is wrong. Let me be more careful.

If A comes first: 
Score = A[1]*m + A[2]*(m-1) + ... + A[m]*1 + B[1]*m + B[2]*(m-1) + ... + B[m]*1
= (A[1]*m + ... + A[m]*1) + (B[1]*m + ... + B[m]*1)

If B comes first:
Score = B[1]*m + ... + B[m]*1 + A[1]*m + ... + A[m]*1  
= (B[1]*m + ... + B[m]*1) + (A[1]*m + ... + A[m]*1)

So both arrangements give the same score. This can't be right.

Let me re-read the problem statement...

Actually, I think I misunderstood how prefix sums work in the final array.

If we have arrays [a,b] and [c,d], and we concatenate them to get [a,b,c,d]:
- S1 = a
- S2 = a+b  
- S3 = a+b+c
- S4 = a+b+c+d

Score = a + (a+b) + (a+b+c) + (a+b+c+d) = 4a + 3b + 2c + 1d

If we have arrays [c,d] and [a,b], and concatenate to get [c,d,a,b]:
- S1 = c
- S2 = c+d
- S3 = c+d+a  
- S4 = c+d+a+b

Score = c + (c+d) + (c+d+a) + (c+d+a+b) = 4c + 3d + 2a + 1b

So we want to maximize: 4a + 3b + 2c + 1d vs 4c + 3d + 2a + 1b
This is equivalent to: (4a + 3b + 2c + 1d) - (4c + 3d + 2a + 1b) = 2a + 2b - 2c - 2d = 2(a+b-c-d)

So we should put array with larger sum first.

But wait, let me double-check with the example:
Arrays [4,4] and [6,1]
Sum of [4,4] = 8
Sum of [6,1] = 7
We want to put [4,4] first (larger sum) → Score = 4*2 + 3*4 + 2*6 + 1*1 = 8 + 12 + 12 + 1 = 33

But the answer is 41. Let me recheck...

Actually, let me be very careful with indexing.

If we have arrays [a,b] and [c,d], final array [a,b,c,d]:
- S1 = a
- S2 = a+b  
- S3 = a+b+c
- S4 = a+b+c+d

Score = 1*a + 2*(a+b) + 3*(a+b+c) + 4*(a+b+c+d)
= 1*a + 2*a + 2*b + 3*a + 3*b + 3*c + 4*a + 4*b + 4*c + 4*d
= (1+2+3+4)*a + (2+3+4)*b + (3+4)*c + 4*d
= 10*a + 9*b + 7*c + 4*d

If we have arrays [c,d] and [a,b], final array [c,d,a,b]:
- S1 = c
- S2 = c+d  
- S3 = c+d+a
- S4 = c+d+a+b

Score = 1*c + 2*(c+d) + 3*(c+d+a) + 4*(c+d+a+b)
= 1*c + 2*c + 2*d + 3*c + 3*d + 3*a + 4*c + 4*d + 4*a + 4*b
= (1+2+3+4)*c + (2+3+4)*d + (3+4)*a + (4)*b
= 10*c + 9*d + 7*a + 4*b

So we want to maximize: 10*a + 9*b + 7*c + 4*d vs 10*c + 9*d + 7*a + 4*b
This is equivalent to: (10*a + 9*b + 7*c + 4*d) - (10*c + 9*d + 7*a + 4*b) = 3*a + 5*b - 5*c - 5*d = 3*a + 5*(b-d) - 5*c

This is getting complex. Let me think of a simpler approach.

## Simpler Insight

Let's say we have two arrays A and B with sums SA and SB respectively.
If A comes first, the contribution to score from A is:
- A[1] contributes 1 time
- A[2] contributes 2 times  
- ...
- A[m] contributes m times
So total contribution = 1*A[1] + 2*A[2] + ... + m*A[m]

The contribution from B (when it comes after A) is:
- B[1] contributes m+1 times
- B[2] contributes m+2 times
- ...
- B[m] contributes 2m times
So total = (m+1)*B[1] + (m+2)*B[2] + ... + (2m)*B[m]

If B comes first, then A comes after B:
Contribution from B = 1*B[1] + 2*B[2] + ... + m*B[m]
Contribution from A = (m+1)*A[1] + (m+2)*A[2] + ... + (2m)*A[m]

So difference is:
(1*A[1] + 2*A[2] + ... + m*A[m]) + ((m+1)*B[1] + ... + (2m)*B[m]) - ((1*B[1] + 2*B[2] + ... + m*B[m])) - ((m+1)*A[1] + ... + (2m)*A[m])
= (1*A[1] + 2*A[2] + ... + m*A[m]) + (m+1)*B[1] + ... + (2m)*B[m] - (1*B[1] + 2*B[2] + ... + m*B[m]) - (m+1)*A[1] - ... - (2m)*A[m]
= (1*A[1] - (m+1)*A[1]) + (2*A[2] - (m+2)*A[2])) + ... + (m*A[m] - (2m)*A[m]) + ((m+1)*B[1] - 1*B[1]) + ... + (2m)*B[m] - m*B[m])
= (-m*A[1]) + (-m*A[2]) + ... + (-m*A[m]) + (m*B[1]) + ... + (m*B[m])
= -m*(A[1] + ... + A[m]) + m*(B[1] + ... + B[m])
= m*(SB - SA)

So we should put array with larger sum first.

Let me verify with example:
Arrays [4,4] and [6,1]
Sum of [4,4] = 8
Sum of [6,1] = 7
Since 8 > 7, we put [4,4] first.
Final array: [4,4,6,1]
Prefix sums: 4, 8, 14, 15  
Score = 4 + 8 + 14 + 15 = 41 ✓

This matches!

## Algorithm

1. For each array, calculate its sum
2. Sort arrays in descending order of their sums
3. Concatenate them in this order
4. Calculate the final score

Let me implement:

```python
def solve():
    n, m = map(int, input().split())
    
    arrays = []
    for i in range(n):
        arr = list(map(int, input().split()))
        arrays.append(arr)
    
    # Calculate sum of each array
    sums = []
    for i in range(n):
        sums.append((sum(arrays[i]), i))
    
    # Sort by sum in descending order
    sums.sort(reverse=True)
    
    # Reconstruct the final array in optimal order
    result = []
    for sum_val, idx in sums:
        result.extend(arrays[idx])
    
    # Calculate score
    score = 0
    prefix_sum = 0
    for i in range(len(result)):
        prefix_sum += result[i]
        score += prefix_sum
    
    return score

t = int(input())
for _ in range(t):
    print(solve())
```

Test output (stdout)

..                                                                       [100%]
2 passed in 0.03s
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.