Winter Cup 6.0 Online Mirror Contest |
---|
Finished |
As Iceberg Corporation kept growing and making significant profit, Yessine went from millionaire to billionaire. He got really greedy and decided to hide his money from the government to avoid taxes. To do so, he decided to put all his money in bags and bury them in Sfax. As you may know from previous Winter Cups, Sfax is an $$$N \times M$$$ rectangular grid. Yessine has $$$K$$$ bags of money. He will hide at most one bag per grid cell. However, he won't place them in random cells. Instead, he will bury a bag in a cell if it maximizes the sum of Manhattan distances from all the other cells in Sfax.
Formally, he wants to maximize $$$S$$$ defined as:
$$$$$$S=\sum\limits_{i=1}^N \sum\limits_{j=1}^M \sum\limits_{k=1}^K D(i,j,k)$$$$$$
where $$$D(i,j,k)$$$ denotes the Manhattan distance between cell ($$$i$$$,$$$j$$$) and the $$$k^{th}$$$ piece.
The Manhattan distance between $$$(x,y)$$$ and $$$(x',y')$$$ is $$$\lvert x'-x \rvert + \lvert y'-y \rvert$$$.
Help Yessine hide the money before the government captures him.
The first line contains an integer $$$1 \le T \le 100$$$ denoting the number of testcases.
Each testcase contains three integers $$$N$$$, $$$M$$$, $$$K$$$ such that $$$1 \le N,M,K \le 2\times 10^{4}$$$ and $$$K \le N \times M$$$.
Print a single integer $$$S$$$: the maximum possible sum.
42 2 12 2 23 3 64 4 12
4 8 102 512
It is guaranteed that within the given constraints, for each test case, the result will not exceed $$$10^{18}.$$$
Name |
---|