$"$In c$++$ Please

For the following problem you are only allowed to use a map. No other data structure $($such as unordered map, hash table, trie, or any other data structure you may find on the Web$)$ will be accepted and you will not get any credit. You will also not get any s if you provide a solution you

may find XM$19$ on the Web, especially on LeetCode. This is a very good problem to tackle to test your understanding of maps for the Final Exam.

LeetCode Problem $677$: Map Sum Pairs:

Implement a MapSum class with insert, and sum functions.

For the function insert, you'll be given a pair of $($string$,$ integer$).$ The string represents the key and the integer represents the value in a map. If the key already exists, then the original key$-$value pair will be overridden to the new one.

For the function sum, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

Example:

Input: insert$(""$apple$"",3),$ Output: Null $($no output is required$).$

Input: sum$(""$ap$""),$ Output: $3($after the previous input, $$ap$$ matches the first two letters of $$apple$,$

therefore return the value $3)$

Input: insert$(""$app$"",2),$ Output: Null $($no output is required$)$

Input: sum$(""$ap$""),$ Output: $5($after previous input, $$ap$$ matches first two letters of entry $$apple$$ and also $$app$,$ therefore sum all matching prefixes, we get $5).$

Use the shell below for your code, no need to add test code, just complete the shell. You may add additional functions as needed, but it isclass MapSum $\{$ public: $/**$ Initialize your data structure here. $*/$ MapSum$()\{//$ default constructor $$ void insert$($string key, int val$)\{//$ function to add a new entry in the map $$ int sum $($string prefix$)\{//$ function to return the sum of all matching prefix values in the map $\}\}$;$"$