时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
wang正在打工,任务是对一些货物进行打包,将一些货物装入若干个箱子里。
这也是有讲究的,在装货过程中,每一个箱子里货物的编号必须是一个连续的区间,并且必须按照物品的编号顺序装入,具体来讲编号为
的箱子一定包含
号物品,编号最大的箱子一定包含
号物品。
每个货物都会有一个重量

,每个箱子的总重量是箱子中所有货物的重量之和,
每个箱子的总重量不能超过wang的承受能力
。另外wang搬动一个箱子需要花费的体力是箱子中重量最大的货物的重量减去重量最小的货物的重量。且每次搬运箱子还需要wang大喊:哇咔咔,这会消耗他

点体力。现在wang想知道自己最少要花费多少体力才能把所有货物分批装入箱子里并且搬运。
你还需要帮助wang回答

个问题,每个问题询问一个区间

,

,wang想知道自己能不能把

到

这个区间的货物装到一个箱子里并且自己可以承受其重量。
输入描述:
第一行两个整数,n,m; 表示n个货物,m个询问。
第二行M,W; M表示为基础体力,W为wang的承受能力。
,
第三行n个货物的重量wi。
接下来4~m+3行为询问的区间,每行两个数字l和r。
输出描述:
共m+1行,其中1~m行为每个区间能否承受,可以的话为"YE5",否则输出"N0",不包含引号。
最后一行输出wang把所有的货物装箱并搬运所需要消耗的最小的体力。
示例2
输入
复制
5 3
3 6
2 3 4 5 1
1 3
2 5
4 5
示例3
输入
复制
5 3
4 6
2 3 4 4 1
1 2
2 3
4 5