問題文

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
• 入力は全て整数

入力例 1

1
0 0
3 2

出力例 1

4

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

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

入力例 2

3
141 592
653 589

出力例 2

171