Grid Satisfaction Problem

In this problem, you are given a grid of size N*M containing two types of people: type ‘A’ and type ‘B’. You are given the number of people of each type: 'countA' denotes the number of type 'A' people, and 'countB' denotes the number of type 'B' people. The satisfaction level of each type of person changes based on the number of neighbors they have:

• Type A starts with an initial satisfaction of 80 and it decreases by 20 for each neighbor.
• Type B starts with an initial satisfaction of 50 and it increases by 10 for each neighbor.

Your task is to determine the maximum possible grid satisfaction.

Example:

Input:

2
N = 2, M = 2, countA = 2, countB = 0
N = 3, M = 3, countA = 1, countB = 1

Output:

120
130

Explanation:

• In the first test case, placing two type 'A' people optimally gives a satisfaction sum of 120.
• In the second test case, placing one type 'A' and one type 'B' optimally gives a satisfaction sum of 130.

Constraints:

• 1 <= T <= 2
• 1 <= N, M <= 6
• 0 <= countA, countB <= min(N*M, 6)

Note that you do not have to fill the entire grid. The number of people for each type can be less than the given 'countA' and 'countB' but cannot exceed them. A person occupies one cell and no cell can have more than one person. Neighbors are cells that are adjacent and share a boundary.