#P10925. Maximum Pancake Area

    ID: 12972 Type: Default 1000ms 256MiB

Maximum Pancake Area

Maximum Pancake Area

Happybob wants to make a pancake using limited ingredients. He has a pan that is shaped like a diagonally oriented square (a "\(\text{斜正方形}\)" pan). The pan is defined by an integer \(n\): it has \(n\) rows, and the number of cells in the \(i\)th row is given by

[ \text{cells}(i)= n-|2i-(n+1)|, \quad 1 \le i \le n. ]

Thus the total number of cells in the pan (its area) is

[ P(n)=\begin{cases}\frac{n^2+1}{2}&\text{if }n\text{ is odd},\[6mm]\frac{n^2}{2}&\text{if }n\text{ is even}.\end{cases} ]

Happybob must make his pancake by covering some cells inside the pan using exactly \(m\) axis‐aligned rectangles (the rectangles cannot overlap and must lie fully within the pan). Your task is to determine the maximum number of cells (i.e. the maximum area) that can be covered by these \(m\) rectangles. Note that the pancake cannot exceed the area of the pan.

A useful observation is that if \(m\) is small (specifically, if \(m

[ R(m)= m(2n-m) ]

cells by optimally placing the rectangles, but the final answer is bounded by (P(n)). In summary, given (n) and (m), the maximum area is

[ \min\Big(P(n),; m(2n-m)\Big) \quad \text{(with the understanding that if } m\ge n \text{ then the entire pan can be covered).}]

Given \(n\) and \(m\), output the maximum number of cells that can be covered.

inputFormat

The input consists of a single line containing two integers \(n\) and \(m\) separated by a space. \(n\) represents the size of the pan and \(m\) represents the number of rectangles.

It is guaranteed that \(n\) and \(m\) are positive integers.

outputFormat

Output a single integer, the maximum number of cells that can be covered by \(m\) rectangles.

sample

5 1
9