Minimizing MST Edge Sum on a Labeled Grid

Given an ( n \times m ) grid, the vertices are denoted by ( (i,j) ) where ( 1 \le i \le n ) and ( 1 \le j \le m ). There is an undirected edge between ( (i, j) ) and ( (i, j+1) ) for ( 1 \le i \le n,\ 1 \le j < m ), and between ( (i, j) ) and ( (i+1, j) ) for ( 1 \le i < n,\ 1 \le j \le m ). Two vertices are considered adjacent if there is an edge connecting them.\n\nYou are to assign each of the ( nm ) vertices a unique label from ( 1 ) to ( nm ). For every edge connecting two adjacent vertices with labels ( a ) and ( b ), define its weight as ( \max{a, b} ). After constructing the weighted graph, consider its Minimum Spanning Tree (MST). Your task is to label the vertices in such a way that the sum of the weights of the MST is minimized.\n\nIt can be shown that the optimal (minimum) MST weight sum is given by the formula:\n\n[ \frac{nm(nm+1)}{2} - 1 ] \nNote: The MST referred here is defined in the standard way; for further details, you may refer to the OI Wiki article on MST.

inputFormat

The input consists of a single line containing two space-separated integers ( n ) and ( m ) (( 1 \le n, m \le 10^5 ) for example), representing the grid dimensions.

outputFormat

Output a single integer: the minimum possible sum of the weights of the MST for the optimally labeled grid.

sample

1 1

0