You are given a grid of size N*M. There are two types of people, type ‘A’ and type ‘B’ . You are also given the number of people of each type say ‘countA’ is the number of ‘A’ type persons and ‘countB’ is the number of ‘B’ type of persons. The satisfaction of a particular type of person can increase or decrease as follows :
The initial satisfaction of a person of type A is 80. It decreases by 20 for each neighbor.
The initial satisfaction of a person of type B is 50. It increases by 10 for each neighbor.
Your task is to determine the maximum possible grid satisfaction.
You may choose exactly how many people you want to be present in the grid.
The total number of people of type ‘A’ living in the grid can be less than ‘countA’ but cannot exceed ‘countA’. Similarly, total number of people of type ‘B’ living in the grid can be less than ‘countB’ but cannot exceed ‘countB’
A person can live in only one cell.
Not more than one person can live in a cell.
Two cells are said to be neighbors if the cells are adjacent and share a boundary.
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first and the only line of each test case contains four space-separated integers ‘N’, ‘M’, ‘countA’, and ‘countB’, denoting the grid’s dimensions and the number of each type of people present.
For each test case, print in a new line an integer denoting the maximum possible grid satisfaction.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 2
1 <= N,M <= 6
0 <= countA, countB <= min(N*M, 6)
Time Limit: 1sec
Sample Input 1:
3 1 0 1
Sample Output 1:
Explanation For Sample Input 1:
In this test case, we can have only one person of type B. Since, this person will have no neighbors, the satisfaction of this person will not change and we will get the maximum grid value of 50.
Sample Input 2:
2 2 1 2
Sample Output 2: