Stacks

Given a list of list of positive integers stacks, you can take any stack(s) in stacks and pop any number of elements. Return the maximum sum that can be achieved such that all stacks have the same sum.

Constraints

• n * m ≤ 500,000 where n and m are the number of rows and columns in stacks

https://binarysearch.com/problems/Stacks

Examples

Example 1

Input

• stacks = [[2, 3, 4, 5], [4, 5, 2, 3, 3], [9, 1, 1, 1]]

Output

• answer = 9

Explanation

Here are the operations we can take

• Pop [5] from the first stack to get [2, 3, 4] for a sum of 9.
• Pop [2, 3, 3] from the second stack to get [4, 5] for a sum of 9.
• Pop [1, 1, 1] from the first stack to get [9] for a sum of 9.

Example 2

Input

• stacks = [[5, 13], [7, 2], [50]]

Output

• answer = 0

Explanation

We have to pop all elements from every stack since there’s no way to make the three stacks have equal sum otherwise.

Solution