#3636. 教义问答手册

内存限制:512 MiB 时间限制:20 Sec

题目描述

“汉中沃野如关中,四五百里烟蒙蒙。黄云连天夏麦熟,水稻漠漠吹秋风。”——摘自 黄裳《汉中行》
“泉岭精神不朽,汉中诸球永生。”——摘自《泉岭精神创立者语录》
“把神犇烤一烤,味道会更好。”——摘自《xhr语录》
“秀恩爱有利于身心健康!”——摘自《泉岭精神集大成者语录》
“楼上说的对!”——摘自《泉岭精神信徒语录合集》
“不会做积分,怎么找妹子!”——摘自《xhr语录》
“切实保护耕地以放置更多的哨戒炮。”——摘自《泉岭精神信徒语录合集》
“就算两个包子一起吃掉,也不能阻止我修筑梯田。”——摘自《泉岭精神创立者语录》
“我来自泉岭,他来自汉中,我们半道而逢。”——摘自《泉岭精神集大成者语录》
【问题描述】
    作为泉岭精神的缔造者、信奉者、捍卫者、传承者,Pear决定印制一些教义问答手册,以满足泉岭精神日益增多的信徒。Pear收集了一些有关的诗选、语录,其中部分内容摘录在了【题目背景】里。这些语录是按出现的时间排好序的——Pear很喜欢这样的作风,于是决定在按时间排好序的基础上,选择部分语录,制作成若干本教义问答手册。
    一共有N条语录。Pear决定从中选出某一段时间内的所有语录,在此基础上印制大小为L的若干本教义问答手册。Pear对印制的手册有如下要求:
    1.每本手册必须包含这个区间内连续的恰好L条语录。
    2.不同手册包含的语录不能相同。
    3.每条语录有一个“主题相关程度”,这个数可正可负。Pear希望所有手册的语录的“主题相关程度”之和尽可能大。
    例如,对于区间[3,15]和L=3,一种选择方法是:[4,6]+[9,11]+[12,14]。这三个区间长度都恰好为L,且互不重叠。
    Pear并没有决定选哪段时间的语录,因此他有Q次询问。每次询问,给出两个数[l,r]表示候选语录的范围是第l条到第r条。你能回答出每个询问的最大“主题相关程度”之和么?

输入格式

    第一行两个正整数N,L,含义如上所述。注意对于所有询问,L都是一样的。
    第二行N个整数,绝对值<=10000。第i个数表示第i条语录的“主题相关程度”。
    接下来Q行,每行两个正整数l和r,表示询问区间。

输出格式

    输出Q行,每行表示这组询问的答案。注意,这个答案可以是0,如果区间负数过于多的话。

样例

样例输入


			
15 3
3 1 5 -2 3 -2 -2 2 2 2 0 3 2 -1 0
9
8 10
10 10
9 11
2 14
5 14
5 13
12 13
7 13
2 10

样例输出


			
6
0
4
17
11
11
0
11
12

数据范围与提示

【数据范围】

    对于10%的数据,N=1000,Q=1000,L<=50

    对于另外20%的数据,N=100000,Q=100000,L<=5

    对于另外20%的数据,N=100000,Q=100000,L<=10

    对于100%的数据,N=100000,Q=100000,L<=50