A32400.最优政府大楼选址-2

"In a world of infinite possibilities, even the smallest decisions—like where to build—must be guided by balance and precision. The right place is not always the center, but the point where all paths converge with purpose."

---

Yorkshire 小镇建立在一个笛卡尔坐标系中的第一象限，小镇的大小是无穷无尽的。在这个小镇中有 $N$ 栋居民楼，每一栋居民楼都有一个坐标，其中第 $i$ 个居民楼坐落在坐标 $(x_i, y_i)$ 处。

这天，小镇居民决定建立一个政府大楼。但政府大楼的选址比较讲究。小镇的每一个居民到任意一个坐标都有一个值 $\epsilon_i$，表示居民走路的意向程度。

你的任务是找出一个有序实数对 $(x, y)$，满足：

$$\mathtt{ANS}_{x, y} = \min_{(x, y)}\sum_{i=1}^{N}{((\lvert x_i-x\rvert + \lvert y_i - y \rvert) \times \epsilon_i)}$$

表示小镇政府大楼的最优选址。

对数学感到头疼的小镇镇长拜托 Macw 找到了你，请你求出小镇政府大楼坐落的最佳坐标 $(x, y)$，并输出 $\mathtt{ANS}_{x, y}$。

Problem credits: Macw07。

输入包含 $N+2$ 行：

第一行输入一个整数 $N$，表示小镇居民楼的数量。
第二行输入 $N$ 个整数，第 $i$ 个整数表示 $\epsilon_i$。
接下来的 $N$ 行每一行输入两个实数。表示某栋居民楼的坐标 $(x_i, y_i)$。

第一行输出一个浮点数，表示答案。

本题采用 $Special \ Judge$，输出结果误差在 $10^{-4}$ 以内即视为合格。

数据范围与约定：

对于 $100\%$ 的数据，保证 $1 \le N \le 5000$。
对于 $100\%$ 的数据，保证 $0 \le \lvert x_i\rvert , \lvert y_i \rvert \le 10^3$。
对于 $100\%$ 的数据，保证 $1\le \epsilon_i \le 10$。
另外，对于前 $20\%$ 的数据，有 $1 \le N \le 30$，且满足 $1 \le \lvert x_i\rvert , \lvert y_i \rvert \le 10$。