8268: BZOJ4268:小强的书架

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

小强有很多书,它想制作一个书架。 对于每本书,它有一个高度、一个厚度。书架的一层能够放置的书的厚度总和不能超过一个 常数W。小强想让每层书架里的书都用一种雅观的方式进行摆放,它经过思考之后认为, 一层书架的高度应该由下式给出: First+Second+(W-s)/10 其中,First和Second分别是这层书架中高度前两高的书的高度(如果这层只有一本书, 那么令First、Second等于这唯一一本书的高度;如果这层有超过一本高度相同的书都是 最高的,那么First、Second都等于这个最高高度),s表示这层书架的厚度的总和。注 意,每层书架的高度可以不一样。 小强把书从1到N编号,它规定,书架的一层中放置的书的编号必须是连续的。小强想知 道,把所有的书都放进去,它的书架至少要多高呢?


输入格式

第一行两个正整数N和W,表示书的数目和一层书架里的书的厚度总和 的上限。N行,每行两个正整数,按编号顺序依次描述了每本书的高度和厚度。输入数据保证每本书 的厚度都不超过W,高度不超过100000000。


输出格式

一行一个数,精确到小数点后一位,表示书架的最小高度。


样例输入

5 10
3 5
7 2
1 3
5 2
6 3

样例输出

19.5

提示

【样例解释】 第一本书自己一层,高度3+3+5/10=6.5,剩下4本书一层,高度7+6+0/10=13。总 共19.5的高度。 【数据规模】 对于100%的测试数据,N<=300000,W<=1000000000


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: