打工装货
时间限制:C/C++/Rust/Pascal 4秒,其他语言8秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

wang正在打工,任务是对一些货物进行打包,将一些货物装入若干个箱子里。

这也是有讲究的,在装货过程中,每一个箱子里货物的编号必须是一个连续的区间,并且必须按照物品的编号顺序装入,具体来讲编号为1的箱子一定包含1号物品,编号最大的箱子一定包含n号物品。

每个货物都会有一个重量w_i,每个箱子的总重量是箱子中所有货物的重量之和,每个箱子的总重量不能超过wang的承受能力W。另外wang搬动一个箱子需要花费的体力是箱子中重量最大的货物的重量减去重量最小的货物的重量。且每次搬运箱子还需要wang大喊:哇咔咔,这会消耗他M点体力。现在wang想知道自己最少要花费多少体力才能把所有货物分批装入箱子里并且搬运。
你还需要帮助wang回答m个问题,每个问题询问一个区间lr,wang想知道自己能不能把lr这个区间的货物装到一个箱子里并且自己可以承受其重量。

输入描述:

第一行两个整数,n,m; 表示n个货物,m个询问。

第二行M,W; M表示为基础体力,W为wang的承受能力。

第三行n个货物的重量wi。

接下来4~m+3行为询问的区间,每行两个数字l和r。

输出描述:

共m+1行,其中1~m行为每个区间能否承受,可以的话为"YE5",否则输出"N0",不包含引号。

最后一行输出wang把所有的货物装箱并搬运所需要消耗的最小的体力。

示例1

输入

复制
1 1
1 1
1
1 1

输出

复制
YE5
1
示例2

输入

复制
5 3
3 6
2 3 4 5 1
1 3
2 5
4 5

输出

复制
N0
N0
YE5
13
示例3

输入

复制
5 3
4 6
2 3 4 4 1
1 2
2 3
4 5

输出

复制
YE5
N0
YE5
16