#3636. 教义问答手册

题目描述

"汉中沃野如关中，四五百里烟蒙蒙。黄云连天夏麦熟，水稻漠漠吹秋风。"----摘自 黄裳《汉中行》
"泉岭精神不朽，汉中诸球永生。"----摘自《泉岭精神创立者语录》
"把神犇烤一烤，味道会更好。"----摘自《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