P10925 Happybob's Pancake (UBC001E)
题目描述
Happybob 想做一块煎饼，他决定在一个 $n$ 行 $n$ 列的斜正方形的锅里做一个煎饼，所以煎饼的大小不能超过斜正方形的大小。
由于原料有限，因此 Happybob 的煎饼必须是 $m$ 个长方形覆盖而成的。
Happybob 想知道，他能制作出的最大的煎饼的面积是多少。
---
**形式化题意：**
用 $m$ 个长方形覆盖大小为 $n$ 的斜正方形，最多覆盖多少个格子？
**斜正方形和覆盖的定义见说明/提示**。
输入格式
无
输出格式
无
说明/提示
### 样例说明
三次询问的方案是：
（方案不唯一）
### 数据范围
$1\le T\le 50$，$1\le n\le 2\times 10^9$，$1\le m\le\lceil\dfrac{n}{2}\rceil$。
---
### 形式化定义
**斜正方形的定义：**
更形式化地，建立直角坐标系，定义一个大小为 $n$ 的**斜正方形**的**中心**为原点。
若 $n$ 为奇数，则该**斜正方形**可以描述为所有以 $\big\{(x, y) \big | |x| + |y| \le \lfloor \frac{n}{2} \rfloor \text{ and } x, y \in \Z\big\}$ 中的点为**正方形**中心的边长为 $1$ 的**正方形格子**组成的组合图形。
若 $n$ 为偶数，则该**斜正方形**可以描述为所有以 $\big\{(x, y) \big | |x| + |y| \le \frac{n}{2} \text{ and } (x + \frac{1}{2}), (y + \frac{1}{2}) \in \Z\big\}$ 中的点为**正方形**中心的边长为 $1$ 的**正方形格子**组成的组合图形。
一个 $n=5$ 的斜正方形（淡蓝色为格子中心）：
一个 $n=6$ 的斜正方形（淡蓝色为格子中心）：
**覆盖方法的定义：**
定义一个长方形 $R$ 覆盖该**斜正方形**，当且仅当 $R$ 为由若干**格子**组成的长方形。
下面是一个覆盖斜正方形的长方形：
下面则**不是**覆盖斜正方形的长方形：
定义一个**格子**被覆盖，当且仅当选择的 $m$ 个覆盖**斜正方形**的长方形中有至少一个完全包含该格子。