24143번 - カンニング対策 (Cheating) 다국어

近年，日本情報オリンピックは受験者数が著しく増加したが，それにつれて不正行為を行う 受験者も増えてしまい，問題となっている．日本情報オリンピックの試験会場は長方形である． 座標軸をそれぞれ試験会場の壁に平行にとり，原点は試験会場の一つの隅とする．

情報オリンピック日本委員会は受験者の不正行為を自動で監視する装置を n 個製作した．そ れぞれの監視装置は，x 軸方向の監視または y 軸方向の監視のいずれかに用いることができる．

• 監視装置 i を x 軸方向の監視に用いるとき，監視装置 i は p_i ≤ y ≤ p_i + d_i の領域にいる 受験者を監視する．
• 監視装置 i を y 軸方向の監視に用いるとき，監視装置 i は p_i ≤ x ≤ p_i + d_i の領域にいる 受験者を監視する．

ただし，d_i, p_i の値は整数であり，それぞれの監視装置について個別に設定できるが，0 ≤ d_i で，d_i が小さいほど精度よく監視することができる．使用しない監視装置があってもよい．

図 1: 監視装置で受験者を監視している様子

情報オリンピック日本委員会は，注意を要する受験者のリストを持っており，それらの受験 者をできるだけ精度よく監視しようと考えた．したがって，図 1 のように，各々の受験者に対 して x 軸方向に監視を行っている監視装置 1 つ以上と，y 軸方向に監視を行っている監視装置 1 つ以上により要注意の受験者を監視しなければならない．さらに，全ての監視装置での d_i の最 大値を d_max としたとき，d_max をできるだけ小さくしなければならない．

善良な受験者であるあなたに，監視装置の個数 n と要注意の受験者の座標が与えられたとき， d_max の最小値を出力するプログラムの作成を依頼する．ただし，受験者は動かないものとし， 監視装置に監視される領域の境界に受験者がいるとき，その受験者は監視されているものとす る．また，受験者の座標は全て異なる．

入力の 1 行目には，2 つの整数 n, m (2 ≤ n ≤ 200, 000， 1 ≤ m ≤ 100, 000) が空白を区切りとして書かれている．これは，製作した監視装置の個数が n 個，要注意の受験者の人数が m 人であることを表す．

続く m 行 (2 行目から m + 1 行目) は要注意の受験者の座標を表す．j + 1 行目 (1 ≤ j ≤ m) には，2 つの整数 x_j, y_j (0 ≤ x_j, y_j ≤ 1, 000, 000, 000) が空白を区切りとして書かれている．これ は，j 人目の要注意の受験者の座標が (x_j, y_j) であることを表す．

出力は，標準出力に行うこと．d_max の最小値を表す 1 つの整数を出力せよ．