P4594 [COCI 2011/2012 #5] BLOKOVI

平面直角坐标系种有 $N$ 个质量为 $m_{i}$ ，长为 $2$，高为 $h$ 的矩形，使得： * 矩形的边缘与坐标轴平行； * 矩形的下层与 $y$坐标不重合，且为以下值：$0,h,2h,3h,\dots,(N-1)h$； * 最低的矩形左下角的坐标为 $(-2,0)$，右下角与原点重合。  定义一个矩阵的 X 中心是其下边的中点的 X 坐标。一个或多个矩形的 X 中心是其 X 中心的加权平均值。它的计算方法为： $$ Xbarycetre=\frac{\sum_{i}m_{i}\times Xcentre(i)}{\sum_{i}m_{i}} $$ 其中 `Xbarycetre` 表示一个或多个矩形的 X 中心，`Xcentre` 表示一个矩阵的 X 中心。 换句话说，其值为每个矩形的质量乘以它的 X 中心之积除以矩形的总质量。 对于每一个矩形，如果它**上面的矩形**的 X 中心与其的 X 中心的距离小于等于 $1$，则称这些矩形组成的排列是稳定的。 例如，左图的排列是不稳定的，因为上面两个矩形的 X 中心到下面的矩形的X中心的距离大于 $1$。而右图的排列是稳定的。 给出所有矩形的质量，求其可以组成的稳定排列中的矩形的最大 X 坐标。 你不能改变矩形的顺序，它们从**基本**低到高给出。

无

无

有 $30\%$ 的数据，矩形的质量从大到小给出。 $2\le N\le 3\times 10^{5}$，$1\le m_{i}\le 10^{4}$。 题目译自 [COCI 2011/2012 #5 T5](https://hsin.hr/coci/archive/2011_2012/contest5_tasks.pdf)。