Description

—“If... I mean, hypothetically.
If I were to die in five days, could you treat me a little more gently?”

The colossal Beast No. 6 will attack the Floating Continent in five days.

Countless calculations yield cruel data showing that only the qualified spirit of the sacred sword Seniorious — Chtholly Nota Seniorious — by opening the Gate of Fairyland, can defend the floating island at the cost of her life.

“At the very least, I also hope I will not disappear, and I want to be remembered by others. I want to leave bonds behind, too.”

It seems the fairy girl Chtholly has little time left.

A young second-class technical officer, administrator of the Fairy Warehouse, and the last human in the world — 威廉·克梅修 (Willem Kmetsch). Centuries ago, he was a prospective hero and mastered all the knowledge required to become one.

With a great battle imminent, adjusting the sacred sword’s state has become an important task.

瑟尼欧里斯（セニオリス）
圣剑的其中之一，在现存的遗迹兵装中，拥有最强大的力量。
拥有非常特殊的资质，只有极少一部分的人才能使用。
由四十一个护符组成。能将所有事物包含不死者都回归「死亡」。

Willem needs to adjust the sword’s state, so he split Seniorious into talismans that form an $n$-by-$m$ matrix.

Each talisman has its own magic value. To test the sword, you need to divide these talismans into two parts, A and B.

Requirements:

1. Every talisman of the sacred sword belongs to exactly one of the two parts.
2. Within each part, the cells must be connected via up, down, left, and right; moreover, for any two cells within the same part, there must be a path between them that uses at most one turn.

For example:

ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＡＡＡＡＡ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＡＡＢＢ
ＡＢＢＢＡ　　ＢＢＡＡＡ　　ＡＡＡＢＢ
ＡＡＢＡＡ　　ＢａＡＡＡ　　ＡＢＢＢＢ
ＡＡＡＡＡ　　ＡＡＡＡＡ　　ＢＢＢＢＢ

　　(1)　　　　　(2)　　　　　(3)　　　　　　

Among these, (1) and (2) are not allowed, while (3) is allowed. In (2), the cells marked a belong to region A; there is no way for those two a cells to reach each other using at most one turn.

Among all valid partitions, what is the minimum possible value of the larger one between the range of region A and the range of region B?

Kind and cute Nephren, quietly observing from the side, softly tells you that the range is defined as the maximum value in the region minus the minimum value.

The night wind blows; the scenery on Island No. 68 looks no different from the forests on the ground. Then again, golden fairies themselves are mysterious beings that appear, grow, and fade within the forest.

Time is running late. Chtholly, who lost the morning training, will return soon. You must quickly adjust the sacred sword with Willem. Do not be late.

Input Format

The first line contains two natural numbers $n, m$.

The next $n$ lines each contain $m$ natural numbers $A_{i,j}$ representing the weights.

Output Format

Output a single integer: the answer.

4 4
1 12 6 11
11 4 2 14
10 1 9 20
4 17 13 10

11

Hint

Explanation of the sample:

1  12 6        11
11 4  2        14
10 1  9        20
4        17 13 10

The partition is not unique; the figure shows one valid partition. The left part has range $12 - 1 = 11$, and the right part has range $20 - 10 = 10$, so the answer takes the larger of the two, $11$. There is no other partition that can make the answer smaller.

Constraints and Conventions

For all weights, $1 \le A_{i,j} \le 10^9$.

“What Are You Doing at the End of the World? Are You Busy? Will You Save Us?”

Translated by ChatGPT 5