高桥诺鲁姆君有无限大的可能。世界上有很多个叫高桥诺鲁姆的人（“诺鲁姆”取自norm，中文为“范数”，这里直接当作绝对值理解就行）。

现在2维平面中有$N$个高桥诺鲁姆君，第$i(1 \le i \le N)$个高桥诺鲁姆君在坐标$(x_i, y_i)$处。每个高桥诺鲁姆君都被分配了一个正整数$c_i$，对于第$i$个高桥诺鲁姆君，向点$(X, Y)$移动所需要的时间是$c_i * \max(|x_i - X|, |y_i - Y|)$。

你现在要做的事情就是求出所有高桥诺鲁姆君都汇聚到同一点所需要的最短时间。这里“最短时间”定义为最晚到达那一点的高桥诺鲁姆君所花费的时间。

所有高桥诺鲁姆君都是一起出发一起运动的，且互不干涉对方的移动。

题目格式和数据范围应该都看得懂，就不赘述了。