Sum Every Element of an N-Dimensional Array Readable Only by Index Lists

You are given an object m of type MultiDimArray that represents an array with an arbitrary number of dimensions. How the elements are stored is hidden; the object exposes only two methods:

• m.getDims() returns a list with the size of each dimension. For a 2 × 2 × 3 array it returns [2, 2, 3].
• m.get(indices) takes a list with one index per dimension and returns the integer stored at that position. For the same array, m.get([0, 1, 2]) returns the element at index 0 of the first dimension, index 1 of the second and index 2 of the third.

Implement arraySum, which returns the sum of all elements of the array.

Function Signature

def arraySum(m: MultiDimArray) -> int:

Rules

• Read the array only through m.getDims() and m.get(indices); the object offers no other access to its elements.
• m.get(indices) accepts a list of exactly len(dims) integers with 0 <= indices[i] < dims[i] for every i, and raises an error for any other list.
• Return the exact integer sum of all elements, counting every position once.
• In the examples, an array is written as its dimension sizes plus its elements in row-major order, meaning the last index changes fastest: for dims = [2, 2, 3] the elements are listed for positions [0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 0], and so on up to [1, 1, 2]. This listing only describes the test input; m does not expose it.

Constraints

• 1 <= len(dims) <= 20
• dims[i] >= 1 for every dimension
• The total number of elements, the product of all dims[i], is at most 2 * 10^5.
• Every element is an integer with -10^9 <= element <= 10^9.
• The sum can reach 2 * 10^14 in absolute value, which is beyond 2^31 - 1 but within ±2^53.

Examples

Example 1

Input:  m with dims = [2, 2, 3] and elements in row-major order [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Output: 78

Here m.getDims() returns [2, 2, 3], m.get([0, 1, 2]) returns 6, and m.get([1, 0, 0]) returns 7. The twelve elements add up to 78.

Example 2

Input:  m with dims = [4] and elements [3, -1, 4, -1]
Output: 5

A one-dimensional array: 3 - 1 + 4 - 1 = 5.

Example 3

Input:  m with dims = [1, 2, 1, 2] and elements in row-major order [1000000000, -5, 1000000000, 1000000000]
Output: 2999999995

The four positions are [0, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0] and [0, 1, 0, 1]. The sum exceeds 2^31 - 1.