You are given four integers m, n, introvertsCount, and extrovertsCount. You have an m $ imes$ n grid, and there are two types of people: introverts and extroverts. There are at most introvertsCount introverts and extrovertsCount extroverts available to be placed on the grid.

You may place at most one person in each cell of the grid, or leave the cell empty. You do not need to place everyone.

The happiness of each person on the grid is determined as follows:

• An introvert starts with $120$ happiness, but loses $30$ happiness for each placed neighbor sharing a vertically or horizontally adjacent cell.

• An extrovert starts with $40$ happiness, and gains $20$ happiness for each placed neighbor sharing a vertically or horizontally adjacent cell.

The total grid happiness is the sum of the happiness of all individuals placed on the grid.

Return the maximum possible grid happiness.

Constraints:

• $1 \leq$ m, n $\leq 5$

• $0 \leq$ introvertsCount, extrovertsCount $\leq \min($m $ imes$ n, $6)$

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.