题意简述
假设你是一家商店的店主。在新一季开始之前，你决定清理商店中的库存商品，因此你打算举行一次大甩卖。
商店中有 $n$ 种不同的商品：第 $i$ 种商品的价格为 $c_i$ 枚金币。每件商品都有一张写着对应价格 $c_i$ 的价签。你决定以如下形式举办甩卖：“我们将所有价格除以 $x$。”形式化地，这意味着你选择一个公因子 $x$，在甩卖期间，第 $i$ 件商品的价格将变为 $\lceil \tfrac{c_i}{x} \rceil$ 枚金币（其中 $\lceil y \rceil$ 表示向上取整）。
为了避免顾客混淆，你需要为所有商品挂上新的价签，但打印新的价签是有成本的。具体来说，每打印一张价签需要花费 $y$ 枚金币。
于是，你想到一个好办法——为什么不利用现有的价签，把它们重新挂到其他商品上呢？这样，你只需要为那些没有匹配价签的商品打印新的价签。
现在只剩一个问题：你应该将价格降低多少，即选择怎样的 $x$？要求 $x$ 是一个严格大于 1 的整数，并且要使得总收益最大。总收益定义为：所有商品的新价格总和减去打印价签的总成本。
请你计算最大可能的总收益。
思路分析
首先，如果我们确定了 $x$，那么所有商品的新价格总和和打印新价签的成本是可以算出来的。
朴素的暴力是 $O(N)$ 的，效率不够，因为外层还在枚举 $x$.
记所有商品的价格的最大值为 $C$。
我们可以发现，$(x(k-1),xk]$ 区间内的价格，在打折之后都会变为 $k$ 枚金币。
也就是说，如果能快速查出价格在 $(x(k-1),xk]$ 之间的商品个数，我们就能使用 $\dfrac{C}{x}$ 次操作计算出新价格总和。同时我们还能顺便求出来需要的新标签的数量。
这个显然可以前缀和完成，$\text{pre}_i$ 表示价格在 $[1,i]$ 之间的商品个数。