D-Brave tower_第四届SCPC中南民族大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一名勇者，前来挑战 $\textbf{Brave~tower}$ 。

勇者从第层开始向最顶层发起冲击，且需要遵守以下规则：第一行输入一个整数 $n(1 \leq n \leq10^5)$ ，代表有 $\text{Brave~tower}$ 共有 $n$ 层。

处于第 $i$ 层时，你可以选择挑战第 $i+1$ 层的 $\textbf{任意}$ 一间房间，同时需要注意的是：虽然勇者的战斗力超强，但因为勇者的精神力为 $k$ ，若当前挑战的魔物的战斗力比前一层击败的魔物战斗力低 $k+1$ 甚至更多，勇者会因为过于轻敌而失败；若当前挑战的魔物的战斗力比前一层击败的魔物战斗力高 $k+1$ 甚至更多，勇者会因为缺少战斗准备而失败。

简而言之，设当前挑战 $A_{i,j_1}$ ，上一层击败 $A_{i-1,j_2}$ ，当 $|A_{i,j_1}-A_{i-1,j_2}|>k$ 时，勇者不能挑战成功。

问勇者 $\textbf{最少}$ 需要多少精神力 $k$ 才能通关 $\textbf{Brave~tower}$ ？

第一行输入一个整数，代表有共有层。
接下来行，每行输入个整数，第行第列的整数，代表第层第间房间魔物的战斗力。

输出一个整数，代表勇者需要的精神力。

示例1

复制

复制

24 30 (9)
42 44 (16)
(14) 35 47
40 (17) 24
(25) 34 33
括号标记为k=8的一种挑战方式