問題文

$xy$ 平面上に点 $P(X_1, Y_1)$ があります。あなたは $P$ に対して以下の操作を $0$ 回以上任意の回数行えます。

• $\lvert a \rvert \le K$ を満たす実数 $a$ を選び、 $P$ の現在の座標を $(x, y)$ として、 $P$ を $(x+a, y-a)$ または $(x+a, y+a)$ に動かす。

$P$ を点 $(X_2, Y_2)$ に移動させるために必要な操作回数の最小値を求めてください。

制約

• $1 \leq K \leq 10^9$
• $-10^9 \leq X_1, Y_1, X_2, Y_2 \leq 10^9$
• 入力は全て整数

入力例 1Copy

1
0 0
3 2

出力例 1Copy

4

移動の一例として、 $(0, 0) \to (1, 1) \to (1.8, 1.8) \to (2.3, 1.3) \to (3, 2)$ が考えられます。

また、 $3$ 回以下の操作で $P$ を $(3, 2)$ に動かすことはできないため、 $4$ を出力します。

入力例 2Copy

3
141 592
653 589

出力例 2Copy

171