Complaints Pile Up

DJ Wookje wanted to show people how good his DJing was. At 3 a.m. he drove a supercar around the apartment complex and started spinning at full volume.

One speaker was not enough to reach artistic heights. So DJ Wookje decided to do wide-area DJing (wide-area dealing).

1. The apartment complex is a 2D grid, and the distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.
2. DJ Wookje placed $N$ speakers, with the $i$-th speaker at $(x_i, y_i)$.
3. Each speaker has a size. If the $i$-th speaker has size $S_i$ and the volume is $V$, its music can be heard at every point within distance $V \times S_i$ of that speaker.
4. The volume can only be set to whole numbers, and every speaker has the same volume.
5. 『 Art is volume. 』

DJ Wookje keeps raising the volume and is getting closer to artistic heights. However, some people who do not appreciate art file complaints when they hear music from two or more speakers at once. So DJ Wookje decided to raise the volume as far as possible without any complaints. If the boundary of a sound range or a boundary point overlaps with another, the music does not count as overlapping.

Feel the art (volume) of DJ Wookje! How large can the art (volume) of DJ Wookje get?

The first line contains the number of speakers $N$.

The second line contains the sizes $S_1, S_2, \ldots, S_N$ in order.

From the third line onward, the $(i+2)$-th line contains the coordinates $x_i, y_i$ of speaker $i$. No two coordinates are the same.

All input values are integers greater than or equal to 1.

Print the maximum size of the art (volume) that DJ Wookje can reach.

• $2 \le N \le 100000$
• $1 \le S_i \le 1000$
• $1 \le x_i, y_i \le 1000000$