配点

満点

100

部分点

20

---

問題文

$N$人の人間が、2次元平面上の格子点にいる。初期状態では各人の座標は異なる。

1ターン目で、各自が上下左右いずれかの方向へちょうど1だけ進む。

2ターン目で、各自が上下左右いずれかの方向へちょうど2だけ進む。

同様に、$i$ターン目には各自が上下左右いずれかの方向へちょうど$i$だけ進む。

これを繰り返し、あるターンの終了時に全員が同時に原点（0,0）へ集まるようにしたい。

最短で何ターン後に全員が原点へ集まれるかを出力せよ。どうやっても全員が同時に原点に集まることができない場合は、-1を出力せよ。

---

入力形式

入力は以下の形式で与えられる。

$N\\\\ x_0\\ y_0\\\\ ...\\\\ x_{N-1}\\ y_{N-1}$

出力形式

最短で何ターン後に全員が原点へ集まれるかの整数を出力せよ。どうやっても全員が同時に原点に集まることができない場合は、-1を出力せよ。

制約

• $2 ≤ N ≤ 10$
• $\-10^9 ≤ x_i,\\ y_i ≤ 10^9$
• $i \\neq j$なら$(x_i, y_i) \\neq (x_j, y_j)$
• 入力値はすべて整数である。

この問題の判定には、20 点分のテストケースのグループが設定されている。 このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす。

• $1 ≤$ 答 $≤ 10$

---

入力例 1

2
6 0
3 3

出力例 1

3

---

入力例 2

2
2 1
-5 0

出力例 2

5

---

Writer: tomerun

---

Source Name

Autumn Fest

---