← 返回题目列表

Codeforces · 1700/A

A. 最佳路径

中文机器翻译题面 查看原题

给你一个表 $$$a$$$,大小为 $$$n \times m$$$。我们将考虑从上到下编号从 $$$1$$$ 到 $$$n$$$ 的表行,以及从左到右从 $$$1$$$ 到 $$$m$$$ 编号的列。我们将第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格表示为 $$$(i, j)$$$。在单元格 $$$(i, j)$$$ 中写有一个数字 $$$(i - 1) \cdot m + j$$$,即 $$$a_{ij} = (i - 1) \cdot m + j$$$。

一只乌龟最初站在单元格 $$$(1, 1)$$$ 中,它想要来到单元格 $$$(n, m)$$$。从单元格 $$$(i, j)$$$ 可以一步转到单元格 $$$(i + 1, j)$$$ 或 $$$(i, j + 1)$$$(如果存在)之一。路径是一个单元序列,其中序列中每两个相邻的单元都满足以下条件:乌龟可以一步从第一个单元到达第二个单元。路径的成本是写入该路径的单元格中的数字的总和。

例如,当 $$$n = 2$$$ 和 $$$m = 3$$$ 时,表格将如上所示。海龟可以走以下路径:$$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3)$$$。这种方式的成本等于$$$a_{11} + a_{12} + a_{13} + a_{23} = 12$$$。另一方面,路径 $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 1)$$$ 和 $$$(1, 1) \rightarrow (1, 3)$$$ 是不正确的,因为在第一条路径中,海龟无法迈出一步 $$$(2, 2) \rightarrow (2, 1)$$$,而在第二条路径中,它也无法迈出一步。步骤 $$$(1, 1) \rightarrow (1, 3)$$$。

您需要告诉海龟从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的路径的最小可能成本。请注意,单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 是路径的一部分。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^4$$$) — 分别是表 $$$a$$$ 的行数和列数。

输出

对于每个测试用例,输出一个整数 - 从单元格 $$$(1, 1)$$$ 到单元格 $$$(n, m)$$$ 的路径的最小可能成本。

示例

输入 #1

7
1 1
2 3
3 2
7 1
1 10
5 5
10000 10000

输出 #1

1
12
13
28
55
85
500099995000

注意

在第一个测试用例中,唯一可能的路径由单个单元格 $$$(1, 1)$$$ 组成。

语句中显示了第二个测试用例中成本最小的路径。

在第四个和第五个测试用例中,从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 只有一条路径。两条路径都会访问表中的每个单元格。