There is an undirected graph consisting of n nodes indexed from $0$ to n $- 1$. You are given an integer array vals of length n, where vals[i] represents the value of node i. You are also given a $2$D integer array edges, where edges[i] = [a_i, b_i] represents an undirected edge between node a_i and node b_i.

Additionally, you are given an integer k.

A star graph is a subgraph containing a center node and at most k of its neighbors. The star sum is the sum of the values of the center node and all included neighbor nodes.

Return the maximum star sum among all possible star graphs in the given graph.

Constraints:

• n $==$ vals.length

• $1 \leq$ n $\leq 10^5$

• $-10^4 \leq$ vals[i] $\leq 10^4$

• $0 \leq$ edges.length $\leq \min($n $\cdot ($n $- 1) / 2, 10^5)$

• edges[i].length $== 2$

• $0 \leq$ a_i, b_i $\leq$ n $- 1$

• a_i $\neq$ b_i

• $0 \leq$ k $\leq$ n $- 1$

Now, 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 of how to solve this problem.

Implement your solution in the following coding playground.