[ABC344] F - Earn to Advance

F - Earn to Advance

Time Limit: 4 sec / Memory Limit: 1024 MB

题面

有一个 行 列的网格。记 为从上往下数第 行、从左往右数第 列的方格。

Takahashi 初始位于方格 ，没有任何金钱。

当 Takahashi 在方格 时，他可以在一次操作中执行以下动作之一：

• 留在原地并增加他的金钱数额 。
• 从他的金钱中支付 并移动到方格 。
• 从他的金钱中支付 并移动到方格 。

他不能采取使他的金钱变为负数或使他走出网格外的行动。

如果 Takahashi 采取最佳策略，他需要多少步才能到达方格？

限制条件

• 所有输入值均为整数。

---

输入

输入以标准格式给出，格式如下：

输出

输出答案。

---

输入样例 1

3
1 2 3
3 1 2
2 1 1
1 2
4 3
4 2
1 5 7
5 3 3

输出样例 1

8

可以通过以下八个步骤到达方格 ：

• 留在方格 并增加金钱 。他现在有 元。
• 支付 元并移动到方格 。他现在有 元。
• 留在方格 并增加金钱 。他现在有 元。
• 留在方格 并增加金钱 。他现在有 元。
• 留在方格 并增加金钱 。他现在有 元。
• 支付 元并移动到方格 。他现在有 元。
• 支付 元并移动到方格 。他现在有 元。
• 支付 元并移动到方格 。他现在有 元。

---

输入样例 2

3
1 1 1
1 1 1
1 1 1
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

输出样例 2

4000000004