奶牛们正在建造过山车!他们希望你的帮助,在保持预算的同时,设计出尽可能有趣的过山车。
过山车将建在长度为L(1≤L≤1000)的长线性陆地上。过山车由N个(1≤N≤10000)不同可互换部件的集合组成。每个分量i具有固定长度W_i(1≤W_i≤L)。由于地形变化,每个部件i只能从X_i位置开始建造(0≤X_i≤L - W_i)。奶牛想把从0开始到L结束的各种过山车组件串在一起,这样每个组件的结束(除了最后一个)就是下一个组件的开始。
每个组件i都有一个“乐趣评级”F_i(1≤F_i≤1000000)和一个成本C_i(1≤C_i≤1000)。压路机的总乐趣是所使用的每个组件的乐趣之和;总成本同样是所使用的每个组件的成本之和。奶牛的总预算为B(1≤B≤1000)。
帮助奶牛确定他们可以用预算建造的最有趣的过山车。