Design a data structure that supports the following operations:

1. Insert a key-value pair:

   1. Each key is a string, and each value is an integer.

   2. If the key already exists, update its value to (overriding the previous value).

2. Return the prefix sum:

   1. Given a string, prefix, return the total sum of all values associated with keys that start with this prefix.

To accomplish this, implement a class MapSum:

• Constructor: Initializes the object.

• void insert (String key, int val): Inserts the key-value pair into the data structure. If the key already exists, its value is updated to the new one.

• int sum (String prefix): Returns the total sum of values for all keys that begin with the specified prefix.

Constraints:

• $1 \leq$ key.length, prefix.length $\leq 50$

• Both key and prefix consist of only lowercase English letters.

• $1 \leq$ val $\leq 1000$

• At most 50 calls will be made to insert and sum.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding on how to solve this problem.

Implement your solution in the following coding playground.