有 n 颗糖果，其中第 i (1 \le i \le n) 颗糖果的原价为 a_i 元。设第 i (1 \le i \le n) 颗糖果的清仓价格为 w_i \in \{1,2\} 元，则它的性价比被定义为 \frac{a_i}{w_i}。
小 R 带了 m 元钱买糖果。采用了以下购买策略购买糖果：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。若他在考虑第 i (1 \le i \le n) 颗糖果时剩余的钱至少为 w_i 元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果的性价比相同，则他会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均相同，则他会先考虑编号较小的糖果。
观察小 R 购买的贪心策略，他一定是先买了前面连续的一段糖果，买到第 u 颗糖果时钱不够了。要想造成他购买的与最优方案不符，只能是在决策第 u 颗糖果是剩余 1 元，此时他会等到下一个 1 元糖果 v 的出现，此时最优答案可能是把最后买到的 1 元糖果 v 和之前买过的一个 1 元糖果 k 删除，替换成 2 元糖果 u，即满足条件 a_u>a_v+a_k，我们要枚举 u 和 v。
我们不用真正计算性价比并排序，而是根据原价 a_i 排序，可以把排序后的序列分成三个部分：（lim 是部分 C 的左端点，稍后介绍求法）
部分 A：第 1 个糖果至第 u-1 个糖果
部分 B：第 u+1 个糖果至第 lim-1 个糖果
部分 C：第 lim 个糖果至第 n 个糖果
三个部分糖果特点如下：
部分 A：都一定是在第 u 颗糖果之前购买
部分 B：若 w_i=1，则是在 u 之前购买；若 w_i=2，则是在 u 之后购买
部分 C：都一定是在第 u 颗糖果之后购买
对于枚举的每一个 (u,v)，开始计算总方案数。
下面确定 B,C 的分界。依据部分 B 糖果的特点，B 中的糖果 i 满足：a_i>\frac{a_u}{2}(w_i=1)，可转化为 2a_i>a_u，如果该式不成立就是部分 C，所以部分 C 的左端点 lim 可以用指针寻找第一个小于等于 a_u 的 2a_i。
较为容易的是糖果 v 后面的部分，可以任选价格，记本段长度 last=n-v+1，方案数为 2^{last}
设 cnt_1 为 A 中 w_i=2 的糖的个数，cnt_2 为 B 中 w_i=1 的糖的个数。
可以发现，我们能在部分 B 中把第 i 颗糖果的价值调整为 1，之前说过，一旦调整为 1 就意味着这颗糖果会在 u 之前被卖，就有可能作为上面式子中的 k。还可以把刚刚的式子转化为 a_k<a_u-a_v，推断随着 v 的不断增大，a_u-a_v 不断增大，a_k 取值的上界会越来越宽松，所以可选的 k 就是部分 B 的一段后缀，且左端点 l 在 v 的增大中越来越靠左，同样可以用指针维护左端点 l。
记可选 k 的区间长度为 len=lim-l，只有可选 k 区间里都填 2 才能合法，所以合法的方案数为 2^{last}C_{lim-2-len}^{m-u}。