GCD to 1 (Hard)

**This is the hard version of the problem. The only difference between this and easy version is that you need to minimize the sum of matrix in this version** Construct a matrix $A$ of size $N*M$ such that the GCD of every row and column is $1$ and the sum of elements of matrix is minimized. The element must be $2<=A_{i, j}<=10^{9}$. If there are multiple answers possible, print any. ### Input -