原本我自己想了一个自认为很简洁的算法，但是只拿了 60 分，我也不想浪费时间去调试，回归最笨的办法，用了 50 多行把这道题给 AC 了。

先把这道题的数据给进行 2 次预处理。

1、在读入的时候，算一下 l 的累加和sum_l，如果sum_l < L，那么就是无解的，直接输出。

2、只用数组记录小于 L 的 l 以及其对应的 c，做一个 cnt 累加计数，并且再 l记录一个累加和，记作 sum。而对于大于等于 L 的 l，我们只需要其对应 c 的最小值即可，记作 min_c。

3、如果 sum < L，意味着把所有单瓶容量小于 L 的饮料都加起来都不够 L，只能采用单瓶容量大于 L 的饮料，其价格最小值我们已经记录了，输出 min_c。

4、如果 sum > L，那么这个问题就变成了 0-1 背包的动态规划问题。跟传统背包问题的区别有二：

一是可选物品不是 n 了，而是 cnt 个；

二是背包上限不是 L 了。因为我们并不是求一个容量 L 的瓶子能装多少瓶饮料。背包的上限到了 （L-1）*2。

想一想这是为什么？

因为我们已经把单瓶容量大于 L 的饮料在第2步筛掉了，现在留下的都是小于 L 的，其最大值就是（L-1）。背包的极限情况就是在已经把饮料装到了（L-1）的时候，再来一瓶（L-1）的，这就是背包的最大值，看数据范围，也才是 4000 而已，把 dp 数组开到这么大，完全不会 MLE。

5、现在背包已经做完了。我们的最优解就在 $dp[cnt][L]～dp[cnt][L*2-2]$ 中的最小值。 如果这样输出你会拿 90 分。

想一想又错在哪了？

6、正确答案是要把刚刚 dp 出来的最优解，跟我们在第 2 步预处理的 min_c 做一下比较。因为一顿 dp 操作之后的最优解，可能还不如直接来一瓶容量大于 L 来的便宜。

7、AC